Identity testing of reversible Markov chains
This work addresses identity testing for reversible Markov chains, which is an incremental improvement over prior methods that required symmetry, potentially benefiting statistical inference in fields like biology or finance.
The paper tackles the problem of identity testing for Markov chain transition matrices using a single trajectory, relaxing the previous restrictive symmetry assumption to the weaker condition of reversibility, and shows that testing is possible if the stationary distributions are close under a separation-related distance, while also providing insights into the distance notion and addressing open questions.
We consider the problem of identity testing of Markov chain transition matrices based on a single trajectory of observations under the distance notion introduced by Daskalakis et al. [2018a] and further analyzed by Cherapanamjeri and Bartlett [2019]. Both works made the restrictive assumption that the Markov chains under consideration are symmetric. In this work we relax the symmetry assumption and show that it is possible to perform identity testing under the much weaker assumption of reversibility, provided that the stationary distributions of the reference and of the unknown Markov chains are close under a distance notion related to the separation distance. Additionally, we provide intuition on the distance notion of Daskalakis et al. [2018a] by showing how it behaves under several natural operations. In particular, we address some of their open questions.