Do Missing-Mass Bounds Survive Real Text?

The missing mass of a sample is the total probability of all words (or items) that never appeared in it. It is the chance that the next token is something you have never seen. Tight bounds on how much the missing mass fluctuates around its average underpin smoothing in language models, vocabulary sizing, and cache-miss estimation. Two decades of theory have sharpened these bounds by exploiting negative dependence: whether one word is seen and whether another is seen are mildly repelling events, because the sample has finite size. That repulsion lets independent-style exponential tail bounds go through. Every paper in this line, however, is purely mathematical or checked only on simulated distributions. Two of them state this openly. Khanloo and Haffari write that "no empirical datasets were used." McAllester and Ortiz leave language-model implications as future work.

This note proposes the missing empirical audit. It also proposes one targeted repair for the failure we expect it to expose. All existing bounds assume tokens are drawn independently from a fixed distribution. Real text is bursty: a word that appears once in a document tends to reappear, so observations clump. Clumping lowers the effective number of independent observations. That could make the bounds anticonservative, meaning they promise tighter concentration than real samples deliver. We will measure how badly each bound under-covers when text is sampled the way it actually arrives, in documents. We then test whether a document-level version of the bound, with documents treated as the independent unit (the blockwise idea of Zhang et al.), restores valid coverage without collapsing into uselessly wide intervals.

Core Claim

Negative-association bounds for the missing mass are stated in terms of the token count $n$. On real corpora sampled by document, the relevant count is much smaller and depends on burstiness. We hypothesize two things. First, all four published bounds hold, and are loose, under the idealized setting where tokens are drawn independently from the corpus's own unigram distribution. Second, the same bounds are violated at moderate deviations once samples consist of whole documents. If this is right, the bounds' tightness has been judged in a regime that does not match how the quantity is used.

The constructive part is to recount the sample by documents rather than tokens. We will build two versions of this recount. One is a provable document-level bound. The other is a plug-in "effective sample size" correction that we test only empirically and do not claim to prove. We will show which of the two is valid and how its width compares with resampling.

Research Program

The theory we audit comes from four papers, which motivate the study and supply the bounds under test. Concentration Inequalities for the Missing Mass and for Histogram Rule Error proves deviation bounds of $e^{-m\epsilon^2}$ for the upper tail and $e^{-\frac{4}{3}m\epsilon^2}$ for the lower tail, using negative association. On the concentration of the missing mass improves the lower-tail constant to 1.92. Novel Bernstein-like Concentration Inequalities for the Missing Mass splits the vocabulary into frequency bands and handles each band separately, using the Lambert W function; this beats Berend–Kontorovich only for small deviations, $\epsilon < 0.045$ upper and $\epsilon < 0.021$ lower. Revisiting Concentration of Missing Mass gives a Rosenthal-type bound built on a variance proxy. The foundational tools are Dubhashi's: negative association in Balls and Bins: A Study in Negative Dependence, and the fact that the joint moment-generating function is bounded by the product of individual ones in Simple Proofs of Occupancy Tail Bounds. Both require each observation to land in exactly one "bin" independently of the others. Bursty documents break that requirement.

The ground-truth setup treats a large corpus as the population. We use WikiText-103, the benchmark used by Adaptive Input Representations for Neural Language Modeling, which keeps article boundaries. We also use a document subsample of HuggingFaceFW/fineweb. The population's type frequencies define the true $p(x)$. For a sample $S$, the missing mass is computed exactly as

$$U(S)=\sum_x p(x)\,\mathbb{I}[x\notin S],$$

where the sum runs over all types $x$ in the population.

We draw samples under three regimes. In the first, tokens are drawn independently from $p$. This is the theorems' own setting, so every bound must hold here; it serves as the sanity check. In the second, whole documents are drawn independently until $n$ tokens are collected. In the third, samples are contiguous spans of the corpus, which mimics reading a stream.

In each regime we run $10^5$ or more Monte Carlo draws at sample sizes from $10^3$ to $10^6$ tokens. From these we estimate $\mathbb{E}[U]$ and the exact tail curve $\Pr[U-\mathbb{E}U\ge\epsilon]$, then overlay each bound. Deviations of order $10^{-2}$ are the regime where the thresholding bound claims its advantage, and $10^5$ draws resolve tail probabilities down to about $10^{-4}$.

The repair works at the document level. Suppose a sample consists of $N_d$ independent documents. Swapping one document changes $U$ by at most $c$, the largest probability mass covered by the types in a single document. McDiarmid's bounded-differences argument then gives a valid bound of $\exp(-2\epsilon^2/(N_d c^2))$. We expect this bound to be valid but loose, because $c$ is driven by a single document.

We will therefore also derive, and test empirically only, a Bernstein-style variant in the spirit of the blockwise decomposition of Kernel Regression in Structured Non-IID Settings. In that paper, correlated samples are grouped into independent blocks. Here the variance term is computed per document rather than using the worst case. As the cheapest candidate we also test plugging an effective sample size $n_{\text{eff}}$, estimated from within-document repetition rates, into the Berend–Kontorovich form.

The contrast with Zhang et al. is deliberate. They use blocks to show that dependence can help regression. We use blocks to test whether dependence silently invalidates bounds that were proved for independent data.

Baselines

The naive reference point is the published bounds used exactly as written, with $n$ set to the token count. This is what a practitioner would do today. For each bound we report, per regime, the ratio of the bound to the empirical tail probability and the empirical coverage of the intervals it implies. A ratio below one means the bound is violated.

The strongest existing analytical competitor depends on the deviation size. Khanloo–Haffari is the claimed winner at small $\epsilon$ and Berend–Kontorovich for larger $\epsilon$. The Rosenthal-type bound of Revisiting Concentration of Missing Mass reports confidence bounds improved by up to a factor of 5, but only in simulated numerical experiments. We found no result on Lacuna reporting any of these bounds on real text. All bounds are computed from the same samples with no tuning, since none has free parameters beyond the confidence level. Our document-level bounds beat them if two things hold. They must keep empirical coverage at or above nominal in the document and span regimes, where we expect the naive bounds to fail. And their intervals must be no more than about twice the width of the true Monte Carlo quantile.

The strongest practical competitor is a bootstrap that resamples documents. It uses the same samples and the same number of draws, 2,000 resamples per sample. We record its coverage and width alongside the bounds.

The ablation isolating our key ingredient keeps each bound's functional form and changes only the counting unit, from tokens to documents or to $n_{\text{eff}}$. Any coverage gain then comes from the recount and not from a new inequality.

Why not just…?

Why not just bootstrap over documents and skip the bounds? This is the serious threat. If document bootstrap achieves nominal coverage and narrower intervals at every sample size, the analytical bounds lose their practical case for this use. Our experiments report exactly that comparison. The bounds may still earn their place at small $N_d$, where resampling a few dozen documents underestimates rare-type variability, and wherever a guarantee is needed without repeated computation. We will state plainly whichever way the data fall.

Why not keep the independence-based bounds and add a safety margin? A fixed margin cannot be calibrated without knowing the burstiness. Burstiness differs between curated Wikipedia prose and web text such as FineWeb, so a margin tuned on one corpus may under-cover on the other. Running both corpora through the same bounds tests this directly. If a single margin works across both, that is a finding worth reporting, and it would make the recount unnecessary.

Why not fit a Zipf law and compute the missing mass parametrically? Parametric fits describe the mean of $U$. They do not describe its fluctuation under document sampling, which is where we expect the independence assumption to fail. We include a Zipf-fitted Monte Carlo interval as an additional baseline. It fails if its coverage drops in the document regime the way the token-level bounds do.

Proposed Experiments

The decisive check comes first. In the independent-token regime, all four published bounds must hold at every $\epsilon$ and $n$. Any violation means our implementation is wrong. Confirming this also produces the first real-vocabulary measurement of how loose each bound is, and whether Khanloo–Haffari actually wins below $\epsilon=0.02$ on Zipfian text.

Second, in the document and span regimes, we report the smallest $\epsilon$ at which each bound is violated. We also plot the ratio of the true tail probability to the bound against a per-corpus burstiness statistic, the average within-document repeat rate.

Third, we test the document-level McDiarmid bound, the blockwise Bernstein variant, and the $n_{\text{eff}}$ plug-in against bootstrap on coverage and width. The main hypothesis is refuted if the naive token-level bounds keep nominal coverage under document sampling. In that case negative-association bounds are robust to burstiness, which is itself a useful result.

As a secondary transfer test we will reuse the Wikipedia access-log setting from Analyzing Count Min Sketch with Conservative Updates. That paper reported a 7.12x memory reduction under an independent-arrivals model and left bursty arrivals open. In a request stream, the missing mass is the probability that the next request is for a never-seen item. Contiguous windows of requests give a bursty regime with no document boundaries, so we can check whether the $n_{\text{eff}}$ recount carries over from text to streams.