# How good is Good-Turing for Markov samples?

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 5 of its 30 references that are in the map.
- First posted on arXiv 3 Feb 2021.

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

- [Mixing time estimation in reversible Markov chains from a single sample path](https://mlsanity.com/paper/1708.07367/) (2017)
- [On Learning Markov Chains](https://mlsanity.com/paper/1810.11754/) (2018)
- [Statistical Estimation of Ergodic Markov Chain Kernel over Discrete State Space](https://mlsanity.com/paper/1809.05014/) (2018)
- [On the Impossibility of Learning the Missing Mass](https://mlsanity.com/paper/1503.03613/) (2015)
- [Entropy Rate Estimation for Markov Chains with Large State Space](https://mlsanity.com/paper/1802.07889/) (2018)

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

- [Just Wing It: Near-Optimal Estimation of Missing Mass in a Markovian Sequence](https://mlsanity.com/paper/2404.05819/) (2024)
- [Estimating stationary mass, frequency by frequency](https://mlsanity.com/paper/2503.12808/) (2025)
- [NOVA: Fundamental Limits of Knowledge Discovery Through AI](https://mlsanity.com/paper/2605.15219/) (2026)
- [Next-token functional estimation](https://mlsanity.com/paper/2609.19529/) (2026)

## Abstract (arXiv)

The Good-Turing (GT) estimator for the missing mass (i.e., total probability of missing symbols) in n samples is the number of symbols that appeared exactly once divided by n. For i.i.d. samples, the bias and squared-error risk of the GT estimator can be shown to fall as 1/n by bounding the expected error uniformly over all symbols. In this work, we study convergence of the GT estimator for missing stationary mass (i.e., total stationary probability of missing symbols) of Markov samples on an alphabet X with stationary distribution [πx:x ∈ X] and transition probability matrix (t.p.m.) P. This is an important and interesting problem because GT is widely used in applications with temporal dependencies such as language models assigning probabilities to word sequences, which are modelled as Markov. We show that convergence of GT depends on convergence of (P~ x)n, where P~ x is P with the x-th column zeroed out. This, in turn, depends on the Perron eigenvalue λ~ x of P~ x and its relationship with πx uniformly over x. For randomly generated t.p.ms and t.p.ms derived from New York Times and Charles Dickens corpora, we numerically exhibit such uniform-over-x relationships between λ~ x and πx. This supports the observed success of GT in language models and practical text data scenarios. For Markov chains with rank-2, diagonalizable t.p.ms having spectral gap β, we show minimax rate upper and lower bounds of 1/(nβ5) and 1/(nβ), respectively, for the estimation of stationary missing mass. This theoretical result extends the 1/n minimax rate for i.i.d. or rank-1 t.p.ms to rank-2 Markov, and is a first such minimax rate result for missing mass of Markov samples.