# Identity testing of reversible Markov chains

arXiv: https://arxiv.org/abs/2105.06347 · HTML: https://mlsanity.com/paper/2105.06347/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 4 of its 41 references that are in the map.
- First posted on arXiv 13 May 2021.

## Builds on (most cited first, 4 of 4)

- [Which Distribution Distances are Sublinearly Testable?](https://mlsanity.com/paper/1708.00002/) (2017)
- [Minimax Testing of Identity to a Reference Ergodic Markov Chain](https://mlsanity.com/paper/1902.00080/) (2019)
- [ℓp Testing and Learning of Discrete Distributions](https://mlsanity.com/paper/1412.2314/) (2014)
- [Testing Symmetric Markov Chains from a Single Trajectory](https://mlsanity.com/paper/1704.06850/) (2017)

## Built on by (most cited first, 4 of 4)

- [Minimax Hypothesis Testing for the Bradley-Terry-Luce Model](https://mlsanity.com/paper/2410.08360/) (2024)
- [On the α-lazy version of Markov chains in estimation and testing problems](https://mlsanity.com/paper/2105.09536/) (2021)
- [Markovletics: Methods and A Novel Application for Learning Continuous-Time Markov Chain Mixtures](https://mlsanity.com/paper/2402.17730/) (2024)
- [A Geometric Reduction Approach for Identity Testing of Reversible Markov Chains](https://mlsanity.com/paper/2302.08059/) (2023)

## Abstract (arXiv)

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.