# On Learning Markov Chains

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

## Key facts

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

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

- [Attention with Markov: A Framework for Principled Analysis of Transformers via Markov Chains](https://mlsanity.com/paper/2402.04161/) (2024)
- [From Self-Attention to Markov Models: Unveiling the Dynamics of Generative Transformers](https://mlsanity.com/paper/2402.13512/) (2024)
- [From Markov to Laplace: How Mamba In-Context Learns Markov Chains](https://mlsanity.com/paper/2502.10178/) (2025)
- [Just Wing It: Near-Optimal Estimation of Missing Mass in a Markovian Sequence](https://mlsanity.com/paper/2404.05819/) (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)
- [Batch Universal Prediction](https://mlsanity.com/paper/2402.03901/) (2024)
- [On the α-lazy version of Markov chains in estimation and testing problems](https://mlsanity.com/paper/2105.09536/) (2021)
- [Low-Rank Tensors for Multi-Dimensional Markov Models](https://mlsanity.com/paper/2411.02098/) (2024)
- [Temporal Robustness in Discrete Time Linear Dynamical Systems](https://mlsanity.com/paper/2505.02347/) (2025)
- [Monitoring State Transitions in Markovian Systems with Sampling Cost](https://mlsanity.com/paper/2510.22327/) (2025)
- [Next-token functional estimation](https://mlsanity.com/paper/2609.19529/) (2026)
- [Information-Theoretic Analysis of Next-Token Prediction under Markovian Data](https://mlsanity.com/paper/2609.34731/) (2026)

## Abstract (arXiv)

The problem of estimating an unknown discrete distribution from its samples is a fundamental tenet of statistical learning. Over the past decade, it attracted significant research effort and has been solved for a variety of divergence measures. Surprisingly, an equally important problem, estimating an unknown Markov chain from its samples, is still far from understood. We consider two problems related to the min-max risk (expected loss) of estimating an unknown k-state Markov chain from its n sequential samples: predicting the conditional distribution of the next sample with respect to the KL-divergence, and estimating the transition matrix with respect to a natural loss induced by KL or a more general f-divergence measure. For the first measure, we determine the min-max prediction risk to within a linear factor in the alphabet size, showing it is Omega(kloglog n / n) and O(k2loglog n / n). For the second, if the transition probabilities can be arbitrarily small, then only trivial uniform risk upper bounds can be derived. We therefore consider transition probabilities that are bounded away from zero, and resolve the problem for essentially all sufficiently smooth f-divergences, including KL-, L2-, Chi-squared, Hellinger, and Alpha-divergences.