# Statistical Estimation of Ergodic Markov Chain Kernel over Discrete State Space

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Sep 2018.

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

- [Attention with Markov: A Framework for Principled Analysis of Transformers via Markov Chains](https://mlsanity.com/paper/2402.04161/) (2024)
- [Large Language Models as Markov Chains](https://mlsanity.com/paper/2410.02724/) (2024)
- [From Self-Attention to Markov Models: Unveiling the Dynamics of Generative Transformers](https://mlsanity.com/paper/2402.13512/) (2024)
- [Adaptive Data Analysis with Correlated Observations](https://mlsanity.com/paper/2201.08704/) (2022)
- [Generalization bounds for mixing processes via delayed online-to-PAC conversions](https://mlsanity.com/paper/2406.12600/) (2024)
- [How good is Good-Turing for Markov samples?](https://mlsanity.com/paper/2102.01938/) (2021)
- [Estimating stationary mass, frequency by frequency](https://mlsanity.com/paper/2503.12808/) (2025)
- [Mathematical Framework for Online Social Media Auditing](https://mlsanity.com/paper/2209.05550/) (2022)
- [Generalization for slowly mixing processes](https://mlsanity.com/paper/2305.00977/) (2023)
- [Information-Theoretic Analysis of Next-Token Prediction under Markovian Data](https://mlsanity.com/paper/2609.34731/) (2026)

## Abstract (arXiv)

We investigate the statistical complexity of estimating the parameters of a discrete-state Markov chain kernel from a single long sequence of state observations. In the finite case, we characterize (modulo logarithmic factors) the minimax sample complexity of estimation with respect to the operator infinity norm, while in the countably infinite case, we analyze the problem with respect to a natural entry-wise norm derived from total variation. We show that in both cases, the sample complexity is governed by the mixing properties of the unknown chain, for which, in the finite-state case, there are known finite-sample estimators with fully empirical confidence intervals.