Id: arxiv/2602.17587 Url: https://arxiv.org/abs/2602.17587 Tags: math.ST, cs.LG, stat.ML Score: 0 Title: Asymptotically Optimal Sequential Testing with Markovian Data Domain: math.ST Source: arxiv Authors: Alhad Sethi, Kavali Sofia Sagar, Shubhada Agrawal, Debabrota Basu, P. N. Karthik Reviews: 0 Subject: math.ST Category: research Comments: 0 Disputed: false Division: math Mentions: 0 Discussed: 0 Published: 2026-02-19 Page: https://delphi.science/r/arxiv/2602.17587 We study one-sided and $α$-correct sequential hypothesis testing for data generated by an ergodic, finite-state 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 non-asymptotic instance-dependent lower bound on the expected stopping time of any valid sequential test under the alternative, which is asymptotically tight. Our novel analysis improves the existing lower bounds, which are either asymptotic or provably sub-optimal in this setting. Our…