Sequential Hypothesis Testing for Markov Chains

We consider sequential hypothesis tests for Markov chains in which the investigator may adaptively abstain from sampling on each time step in exchange for a reduced sampling cost. This allows the investigator to strategically choose to allow the chain to evolve until it is likely in a state which discriminates well among the hypotheses–when it becomes worth paying the full sampling cost. We first explore the reduction of this problem formulation to several standard hypothesis testing scenarios via an appropriate choice of parameters. Then we derive a dynamic programming characterization of the optimal algorithm in this setting and solve it numerically for several model problems that exhibit the rich, interesting behavior that arise from this modification of the hypothesis testing problem.