Search papers, labs, and topics across Lattice.
This paper studies one-sided and $\alpha$-correct sequential hypothesis testing for data generated by an ergodic Markov chain, where the null and alternative hypotheses correspond to disjoint sets of transition matrices. The authors derive a tight, non-asymptotic, instance-dependent lower bound on the expected stopping time of any valid sequential test under the alternative, improving upon existing asymptotic or suboptimal bounds by incorporating both the stationary distribution and transition structure. They then propose an optimal test whose expected stopping time asymptotically matches this lower bound as $\alpha \to 0$, demonstrating its utility in applications like detecting model misspecification in MCMC and testing structural properties in MDPs.
Optimal sequential hypothesis testing with Markovian data is now possible, thanks to a new lower bound that incorporates both stationary distribution and transition structure, leading to an asymptotically optimal test.
We study one-sided and $α$-correct sequential hypothesis testing for data generated by an ergodic Markov chain. The null hypothesis is that the unknown transition matrix belongs to a prescribed set $P$ of stochastic matrices, and the alternative corresponds to a disjoint set $Q$. We establish a tight non-asymptotic instance-dependent lower bound on the expected stopping time of any valid sequential test under the alternative. Our novel analysis improves the existing lower bounds, which are either asymptotic or provably sub-optimal in this setting. Our lower bound incorporates both the stationary distribution and the transition structure induced by the unknown Markov chain. We further propose an optimal test whose expected stopping time matches this lower bound asymptotically as $α\to 0$. We illustrate the usefulness of our framework through applications to sequential detection of model misspecification in Markov Chain Monte Carlo and to testing structural properties, such as the linearity of transition dynamics, in Markov decision processes. Our findings yield a sharp and general characterization of optimal sequential testing procedures under Markovian dependence.
