Minimax Testing of Identity to a Reference Ergodic Markov Chain
This provides an efficient testing procedure for Markov chain identity verification, which is incremental as it builds on existing testing frameworks.
The paper tackles the problem of testing whether an unknown Markov chain is identical to or far from a given reference chain using a single state sequence, obtaining nearly matching upper and lower sample complexity bounds based on total variation distance. The result shows that sample complexity depends only on the reference chain's properties, not the unknown chain.
We exhibit an efficient procedure for testing, based on a single long state sequence, whether an unknown Markov chain is identical to or $\varepsilon$-far from a given reference chain. We obtain nearly matching (up to logarithmic factors) upper and lower sample complexity bounds for our notion of distance, which is based on total variation. Perhaps surprisingly, we discover that the sample complexity depends solely on the properties of the known reference chain and does not involve the unknown chain at all, which is not even assumed to be ergodic.