# Minimax Testing of Identity to a Reference Ergodic Markov Chain

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 31 Jan 2019.

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

- [Optimal detection of the feature matching map in presence of noise and outliers](https://mlsanity.com/paper/2106.07044/) (2021)
- [Identity testing of reversible Markov chains](https://mlsanity.com/paper/2105.06347/) (2021)
- [On the α-lazy version of Markov chains in estimation and testing problems](https://mlsanity.com/paper/2105.09536/) (2021)
- [Mathematical Framework for Online Social Media Auditing](https://mlsanity.com/paper/2209.05550/) (2022)
- [Matching Map Recovery with an Unknown Number of Outliers](https://mlsanity.com/paper/2210.13354/) (2022)
- [A Geometric Reduction Approach for Identity Testing of Reversible Markov Chains](https://mlsanity.com/paper/2302.08059/) (2023)
- [Reframing Data Value for Large Language Models Through the Lens of Plausibility](https://mlsanity.com/paper/2409.00284/) (2024)

## Abstract (arXiv)

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.