On the Concentration of the Missing Mass

Daniel Berend, Aryeh Kontorovich

Abstract

A random variable is sampled from a discrete distribution. The missing mass is the probability of the set of points not observed in the sample. We sharpen and simplify McAllester and Ortiz's results (JMLR, 2003) bounding the probability of large deviations of the missing mass. Along the way, we refine and rigorously prove a fundamental inequality of Kearns and Saul (UAI, 1998).

Introduction

In statistical inference, particularly when dealing with large or unknown alphabets, a recurring challenge is estimating the "missing mass." When sampling from a discrete distribution—such as words in a language or species in an ecosystem—the missing mass represents the total probability of all outcomes that have not yet appeared in the sample. Estimating this value is a cornerstone of Good-Turing estimation and has profound implications for linguistics, ecology, and machine learning.

While the expected value of the missing mass is well-understood, characterizing its concentration—how much the actual missing mass in a specific sample deviates from its expectation—has proven mathematically difficult. This paper provides a rigorous foundation for these concentration bounds, sharpening existing results and proving a fundamental inequality that had remained unverified for over two decades.

The Problem: Beyond Worst-Case Bounds

To understand the concentration of the missing mass, researchers typically look for "large deviation" bounds. These bounds tell us the probability that the missing mass is significantly higher or lower than its average. Previous attempts often relied on general-purpose tools like Hoeffding’s inequality. However, Hoeffding’s is a "worst-case" bound; it only considers the range of the random variables, often leading to estimates that are too loose for practical use.

A more refined tool, the Kearns-Saul inequality, was proposed in 1998. It is "distribution-sensitive," providing much tighter bounds when the underlying probabilities are far from 1/2. Despite its utility in neural network analysis and inference, the inequality lacked a formal, rigorous proof until this work.

Methodology

The authors' approach to sharpening missing mass bounds involves two primary mathematical breakthroughs:

1. Proving the Kearns-Saul Inequality

The original path to proving the Kearns-Saul inequality involved solving a complex transcendental equation regarding a specific derivative. The authors bypassed this hurdle by employing a convexity argument. By demonstrating that the second derivative of the relevant function is non-negative, they established the inequality through the lens of mathematical convexity, providing the first formal proof of Theorem 4.

2. Leveraging Negative Association

The missing mass is composed of indicator variables (whether a specific item was seen or not). These variables are not independent; observing one item slightly decreases the probability of observing another. However, they satisfy a property known as "negative association." The authors utilized this property to treat these dependent variables as if they were independent, allowing for the application of their newly proven Kearns-Saul bound to the missing mass problem.

Key Results

The paper's theoretical contributions result in significantly tighter and more accessible bounds for the missing mass:

  • Sharper Lower Tail Bound: The authors established a new lower tail estimate (Theorem 2). They improved the constant in the exponent from approximately 1.36 (the previous state-of-the-art) to approximately 1.92. This indicates that the missing mass is more tightly concentrated around its mean than previously believed.
  • Simplified Proofs: Previous sharp results for the missing mass relied on a "thermodynamic approach," which is mathematically dense and difficult to generalize. This paper achieves superior results using direct probabilistic tools, making the proofs more transparent and easier to verify.
  • Upper Tail Recovery: The authors recovered the known upper tail estimates but did so with a significantly streamlined proof structure, unifying the treatment of both tails.

Conclusion and Future Work

By providing the first rigorous proof of the Kearns-Saul inequality and applying it via negative association, this work simplifies and improves the concentration analysis of the missing mass. While the authors successfully established the inequality through convexity, they note that the original mathematical path proposed by Kearns and Saul—involving the specific properties of the first derivative—remains an intriguing open mystery.

Future research may explore the computational implications of these sharper bounds in real-time inference systems, where more precise estimates of unobserved data could improve the performance of language models and ecological predictors.

Summary updated

Abstract

A random variable is sampled from a discrete distribution. The missing mass is the probability of the set of points not observed in the sample. We sharpen and simplify McAllester and Ortiz's results (JMLR, 2003) bounding the probability of large deviations of the missing mass. Along the way, we refine and rigorously prove a fundamental inequality of Kearns and Saul (UAI, 1998).
BibTeX
@inproceedings{berend2013concentration,
  author = {Daniel Berend and Aryeh Kontorovich},
  title = {{On the Concentration of the Missing Mass}},
  booktitle = {Electronic},
  year = {2013},
  doi = {10.1214/ecp.v18-2359},
}
Figure