![[2602.17587] Asymptotically Optimal Sequential Testing with Markovian Data](https://arxiv.org/static/browse/0.3.4/images/arxiv-logo-fb.png){kind=logo}
[2602.17587] Asymptotically Optimal Sequential Testing with Markovian Data
Summary
This paper presents a novel approach to sequential hypothesis testing for Markovian data, establishing new lower bounds and proposing an optimal test that enhances existing methodologies.
Why It Matters
The findings of this research are significant for statisticians and data scientists working with Markov chains, as they provide a more efficient framework for sequential testing. This can lead to improved detection of model misspecifications and better understanding of transition dynamics in various applications.
Key Takeaways
- Introduces a non-asymptotic lower bound for sequential testing under Markovian data.
- Proposes an optimal test that achieves the established lower bound asymptotically.
- Demonstrates applications in model misspecification detection and testing structural properties.
Mathematics > Statistics Theory arXiv:2602.17587 (math) [Submitted on 19 Feb 2026] Title:Asymptotically Optimal Sequential Testing with Markovian Data Authors:Alhad Sethi, Kavali Sofia Sagar, Shubhada Agrawal, Debabrota Basu, P. N. Karthik View a PDF of the paper titled Asymptotically Optimal Sequential Testing with Markovian Data, by Alhad Sethi and 4 other authors View PDF HTML (experimental) Abstract:We study one-sided and $\alpha$-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 $\alpha \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 ...
