# Just Wing It: Near-Optimal Estimation of Missing Mass in a Markovian Sequence

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 58 references that are in the map.
- First posted on arXiv 8 Apr 2024.

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

- [Calibrated Language Models Must Hallucinate](https://mlsanity.com/paper/2311.14648/) (2023)
- [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)
- [On the Impossibility of Learning the Missing Mass](https://mlsanity.com/paper/1503.03613/) (2015)
- [How good is Good-Turing for Markov samples?](https://mlsanity.com/paper/2102.01938/) (2021)
- [Rediscovery of Good-Turing estimators via Bayesian nonparametrics](https://mlsanity.com/paper/1401.0303/) (2014)
- [On the α-lazy version of Markov chains in estimation and testing problems](https://mlsanity.com/paper/2105.09536/) (2021)

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

- [Estimating stationary mass, frequency by frequency](https://mlsanity.com/paper/2503.12808/) (2025)
- [Leave a Window Out: Modifying the Jackknife for Predictive Inference in Time Series](https://mlsanity.com/paper/2605.30292/) (2026)
- [Multiscale replay: A robust algorithm for stochastic variational inequalities with a Markovian buffer](https://mlsanity.com/paper/2601.01502/) (2026)
- [Next-token functional estimation](https://mlsanity.com/paper/2609.19529/) (2026)
- [Forecasting Corpus-Sampling Disagreement in Masked Text Reconstruction](https://mlsanity.com/paper/2610.12987/) (2026)

## Abstract (arXiv)

We study the problem of estimating the stationary mass -- also called the unigram mass -- that is missing from a single trajectory of a discrete-time, ergodic Markov chain. This problem has several applications -- for example, estimating the stationary missing mass is critical for accurately smoothing probability estimates in sequence models. While the classical Good--Turing estimator from the 1950s has appealing properties for i.i.d. data, it is known to be biased in the Markovian setting, and other heuristic estimators do not come equipped with guarantees. Operating in the general setting in which the size of the state space may be much larger than the length n of the trajectory, we develop a linear-runtime estimator called Windowed Good--Turing (WingIt) and show that its risk decays as widetildeO(mathsfTmix/n), where mathsfTmix denotes the mixing time of the chain in total variation distance. Notably, this rate is independent of the size of the state space and minimax-optimal up to a logarithmic factor in n / mathsfTmix. We also present an upper bound on the variance of the missing mass random variable, which may be of independent interest. We extend our estimator to approximate the stationary mass placed on elements occurring with small frequency in the trajectory. Finally, we demonstrate the efficacy of our estimators both in simulations on canonical chains and on sequences constructed from natural language text.