Abstract: Estimating the total probability of unseen outcomes, known as the "missing mass," is a cornerstone of statistical inference in fields ranging from linguistics to ecology. This paper investigates whether the missing mass can be learned in a distribution-free PAC (Probably Approximately Correct) framework using relative error. We prove that such learning is mathematically impossible: for any estimator, there exist distributions where the relative error remains high regardless of sample size. This result formalizes the necessity of structural assumptions, such as heavy-tailedness, for reliable rare-event prediction.
Introduction
When sampling from an unknown discrete distribution, the missing mass is the sum of probabilities of all outcomes not yet observed. Accurate estimation of this quantity is vital for "smoothing" in language models and biodiversity estimation in ecology. While the Good-Turing estimator, developed during WWII, is a standard tool for this task, its performance on arbitrary distributions has been a subject of long-standing debate. This work addresses a fundamental question: Can any algorithm guarantee a low relative error for the missing mass across all possible distributions without prior knowledge?
Methodology: The Coupling Argument
The core of the impossibility result lies in a rigorous mathematical proof using a coupling argument combined with a construction called a $\beta$-dithered geometric distribution. The authors create a family of distributions based on the geometric distribution but slightly perturbed (dithered) at the tails.
By coupling two different distributions in this family, the authors demonstrate that they can generate identical sample sequences with high probability. However, despite producing the same data, these distributions possess significantly different actual missing masses. Because an estimator cannot distinguish between the two based on the observed samples, it is forced to make a large relative error on at least one of them.
Key Insights: The Tyranny of Relative Error
The study highlights that relative error is a much stricter criterion than additive error. In additive error, an estimate off by 0.01 might be acceptable; however, in relative error, being off by 10% when the true value is $10^{-6}$ requires an extremely high level of precision.
As the missing mass decreases, the margin for error shrinks proportionally, making light-tailed distributions (like the geometric distribution) particularly volatile. The paper formalizes the statistical folklore that predicting rare events requires "heavy-tailed" distributions (e.g., power laws) where the tail behavior is more stable and predictable from samples.
Principal Results
- Theorem 2 (The Impossibility Result): The authors prove that for any estimator, there exists a distribution where the relative error exceeds a constant $\epsilon$ with probability greater than $\epsilon$. This effectively precludes the existence of a universal, distribution-free learner for missing mass under relative error.
- Theorem 9 (Generalization): This impossibility extends to continuous tail estimation, proving that predicting the probability that a future sample will exceed the maximum value seen so far is also distribution-free impossible.
- Concrete Bounds: The impossibility holds even for very small relative errors, such as $\epsilon = 10^{-4}$, suggesting the barrier is not merely theoretical but practically significant.
Conclusion and Future Work
The failure of the Good-Turing estimator on certain distributions is not a flaw in the algorithm but a reflection of a fundamental information-theoretic barrier. No algorithm can perform better without additional information about the distribution's structure. Future research is needed to precisely map the boundary between learnable (heavy-tailed) and unlearnable (light-tailed) families and to develop estimators that "fail gracefully" when their underlying assumptions are violated.
Summary updated