# On the Impossibility of Learning the Missing Mass

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Mar 2015.

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

- [Conformal Prediction Beyond the Seen: A Missing Mass Perspective for Uncertainty Quantification in Generative Models](https://mlsanity.com/paper/2506.05497/) (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)
- [Mean-Squared Accuracy of Good-Turing Estimator](https://mlsanity.com/paper/2104.07029/) (2021)
- [Bayesian nonparametric estimation of coverage probabilities and distinct counts from sketched data](https://mlsanity.com/paper/2209.02135/) (2022)
- [Confidence Intervals for Unobserved Events](https://mlsanity.com/paper/2211.03052/) (2022)
- [Cross-Entropy Risk Estimation for Language Models: Inconsistency Must Be Dense, and the Holdout Method Is No Exception](https://mlsanity.com/paper/2608.15798/) (2026)

## Abstract (arXiv)

This paper shows that one cannot learn the probability of rare events without imposing further structural assumptions. The event of interest is that of obtaining an outcome outside the coverage of an i.i.d. sample from a discrete distribution. The probability of this event is referred to as the "missing mass". The impossibility result can then be stated as: the missing mass is not distribution-free PAC-learnable in relative error. The proof is semi-constructive and relies on a coupling argument using a dithered geometric distribution. This result formalizes the folklore that in order to predict rare events, one necessarily needs distributions with "heavy tails".