On the concentration of the missing mass
Open accessAbstract
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).
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
For any distribution and n≥1, the missing mass exceeds its mean by ε with probability at most e^{-ε^2 n}, and falls below its mean by ε with probability at most e^{-1.92 ε^2 n}.
“Pr 𝑠∼D 𝑛 [𝑀 D (𝑠) ≥ 𝑀 𝑛 D + 𝜀] ≤ 𝑒 -𝜀 2 𝑛 (11 ) Pr 𝑠∼D 𝑛 [𝑀 D (𝑠) ≤ 𝑀 𝑛 D -𝜀] ≤ 𝑒 -1.92𝜀 2 𝑛(12)”
From Calibrated Language Models Must Hallucinate (2024) · cites this paper as Berend and Kontorovich [4]
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Cites
No references could be resolved yet.
Research works printed but not linked: 9
- Devdatt Dubhashi and Desh Ranjan. Balls and bins: a study in negative dependence. Ran- dom Struct. Algorithms, 13(2):99-124, September 1998. MR-1642566
- Wassily Hoeffding. Probability inequalities for sums of bounded random variables. American Statistical Association Journal, 58:13-30, 1963. MR-0144363
- Michael J. Kearns and Lawrence K. Saul. Large deviation methods for approximate proba- bilistic inference. In UAI, 1998.
- Andreas Maurer. Thermodynamics and concentration. Bernoulli, 18(2):434-454, 2012. MR- 2922456
- David A. McAllester and Luis E. Ortiz. Concentration inequalities for the missing mass and for histogram rule error. Journal of Machine Learning Research, 4:895-911, 2003. MR- 2076001
- David A. McAllester and Robert E. Schapire. On the convergence rate of good-turing esti- mators. In COLT, 2000.
- Andrew Y. Ng and Michael I. Jordan. Approximate inference algorithms for two-layer bayesian networks. In NIPS, 1999.
- XuanLong Nguyen and Michael I. Jordan. On the concentration of expectation and approxi- mate inference in layered networks. In NIPS, 2003.
- Maxim Raginsky and Igal Sason. Concentration of Measure Inequalities in Information The- ory, Communications and Coding. arXiv:1212.4663, 2012. · arXiv
Cited by
Sorted by citations
Calibrated Language Models Must Hallucinate
Kalai, A. T., & Vempala, S. S. (2024) · Proceedings of the 56th Annual ACM Symposium on Theory of Computing · doi:10.1145/3618260.3649777 · Cited by 91 · see citing works
“where 𝐻 : = 𝑌 \ 𝐹 and 𝑈 : = 𝑌 \ 𝑂 .”
- Authors
- Berend, D., & Kontorovich, A.
- Affiliations
- Ben-Gurion University of the Negev (IL)
- Venue
- Electronic Communications in Probability
- Publisher
- Institute of Mathematical Statistics
- Published
- 2013-01-01
- Volume
- 18
- Issue
- none
- Pages
- 1-7
- ISSN
- 1083-589X (ISSN-L)
- OpenAlex
- W2074154707
- Cited by
- 110
- References
- 0
- Citations by year
- 2025: 1 · 2024: 4 · 2023: 4 · 2022: 6 · 2021: 5 · 2020: 59 · 2019: 7 · 2018: 4 · 2017: 7 · 2016: 1 · 2015: 6 · 2014: 2 · 2013: 3 · 2012: 1
- FWCI
- 3.53
- Type
- journal article
- Language
- en
- Open access
- gold
- doi.org
- Licence
- cc-by
- Locations
- Electronic Communications in Probability (publishedVersion, cc-by)
- Project Euclid (Cornell University) (submittedVersion)
- Funders
- Israel Science Foundation (1141/12)
- Topics
- Physical Sciences › Mathematics › Statistics and Probability › Probability and Statistical Research
- Physical Sciences › Computer Science › Artificial Intelligence › Machine Learning and Algorithms
- Physical Sciences › Mathematics › Statistics and Probability › Statistical Methods and Inference
- Keywords
- missing mass, large deviations, discrete distributions, random sampling, concentration inequalities
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
