📊 statistics

Confidence intervals for maximum unseen probabilities, with application to sequential sampling design

This paper develops nonasymptotic, distribution-free confidence bounds for the maximum unseen probability in Bernoulli product models under both bounded and unbounded alphabet regimes, establishing their near-optimality and applying them to construct sequential sampling stopping rules with finite-sample guarantees.

Original authors: Alessandro Colombi, Mario Beraha, Amichai Painsky, Stefano Favaro

Published 2026-01-29

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Alessandro Colombi, Mario Beraha, Amichai Painsky, Stefano Favaro

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a detective trying to solve a mystery in a massive, dark warehouse filled with thousands of different types of hidden objects. You have a flashlight, but it's not very bright, and you can only see if an object is present or absent in a specific spot. You've walked around and checked many spots, but you haven't seen everything yet.

The big question is: How dangerous is it to stop looking?

Specifically, is there a "monster" (a very common object) hiding in the dark that you just haven't found yet? Or are the things you haven't found just tiny, harmless dust motes?

This paper, written by Alessandro Colombi and colleagues, provides a mathematical toolkit to answer that question. It helps you decide when you can safely stop searching, even when you haven't seen every single item in the warehouse.

Here is a breakdown of their ideas using simple analogies:

1. The Core Problem: The "Unseen" Danger

In many real-world situations (like checking for rare diseases, finding bugs in computer code, or counting rare animals), we often see a lot of common things but miss the rare ones.

The Trap: If you look at 100 patients and see no one with a specific disease, you might think, "Great, the risk is zero!" But that's dangerous. Maybe the disease is just very rare, or maybe you just got lucky and didn't look at the right people.
The Goal: The authors want to calculate a "safety ceiling." They want to say: "I am 95% sure that the most common thing I haven't seen yet is no bigger than X." If X is small enough, you can stop looking. If X is still huge, you need to keep searching.

2. Two Different Types of Warehouses

The paper realizes that the "warehouse" (the universe of possibilities) comes in two flavors, and you need different flashlights for each:

The Bounded Warehouse (Finite): You know exactly how many types of objects exist (e.g., there are exactly 1,000 species of birds).
- The Old Way: The standard rule is very cautious. It assumes the worst-case scenario: "Maybe all 1,000 birds are hiding!" This leads to a very wide safety ceiling, meaning you have to search for a long time to feel safe.
- The New Way: The authors created a smarter rule. If you've already seen 900 birds, the rule realizes, "Okay, we only need to worry about the remaining 100." This tightens the safety ceiling, letting you stop sooner if the data supports it.
The Unbounded Warehouse (Infinite): You don't know how many types of objects exist. There could be 1,000, or there could be a million, or an infinite number of them (like trying to count every possible typo in a language).
- The Bad News: The authors proved a surprising fact: You cannot make a safe guess if you don't look at the data. If you try to set a rule that works for any possible infinite warehouse without looking at what you've actually found, you will fail. The "safety ceiling" could be anything from zero to 100%.
- The Good News: If you look at your data, you can build a smart, adaptive rule. If you've seen a lot of variety, the rule adjusts. If you've only seen a few things, the rule stays wide. They proved this new method is the best possible way to handle infinite possibilities.

3. The "Rule of Thumb" for Choosing

The paper also gives a simple way to decide which flashlight to use when you aren't sure if the warehouse is finite or infinite.

The Visual Test: Imagine a graph showing how many new things you find as you keep searching.
- If the line goes up fast and then flattens out (like a plateau), you've probably found almost everything. Use the "Bounded" method.
- If the line keeps climbing slowly (like a gentle slope), there are likely many more hidden things. Use the "Unbounded" method.
The Math Test: They also provide a quick calculation. If the total "weight" of the things you've seen is small compared to the number of things you could have seen, assume the warehouse is huge (Unbounded).

4. Why This Matters (The "Contamination" Problem)

In the real world, data is often messy. Imagine you are looking for rare birds, but your camera keeps taking pictures of random dust specks that look like birds. These are "fake" rare items (artifacts).

Old methods often get confused by these fakes. They see thousands of "rare" dust specks and think, "Wow, there are so many rare things I haven't found! I need to search forever!"
The authors' new method is robust. It can tell the difference between a few truly hidden, common monsters and a sea of fake, tiny dust specks. It doesn't panic when the data gets noisy.

5. Real-World Test: Cancer Genomics

To prove their method works, they tested it on real data from the TCGA (The Cancer Genome Atlas), which catalogs genetic mutations in cancer patients.

The Situation: There are billions of possible genetic mutations. Most are extremely rare (appearing in only one patient).
The Result: Their method successfully calculated how likely it is to find a new, common mutation in future patients. It showed that even though there are billions of possibilities, the "safety ceiling" for unseen mutations was low enough to be useful for researchers, provided they used the right "Unbounded" approach.

Summary

This paper is about knowing when to stop looking.
It teaches us that:

If you know the total number of possibilities, you can be smarter about your search.
If the possibilities are infinite, you must look at your data to make a safe guess; a generic rule won't work.
Their new math tools are tougher against "noise" (fake data) and help scientists stop wasting time searching for things that are likely just tiny, harmless dust motes, rather than dangerous monsters.

Technical Summary: Confidence Intervals for Maximum Unseen Probabilities

Problem Statement

The paper addresses the statistical challenge of determining whether additional sampling is necessary to detect all categories whose prevalence exceeds a prespecified threshold $\varepsilon$ . This problem arises in domains such as ecology, genomics, security analysis, and language modeling, where the goal is to ensure that no unobserved outcome has a probability mass greater than $\varepsilon$ .

The authors formalize this within a Bernoulli product (incidence) model. In this setting, for a set of symbols (categories) $j \in \{1, \dots, M\}$ and sampling units $i \in \{1, \dots, n\}$ , observations are binary indicators $X_{ij}$ representing the presence or absence of symbol $j$ in unit $i$ . The incidence probabilities $p_j$ are constant across units. The alphabet size $M$ can be finite (bounded) or countably infinite (unbounded).

The inferential target is the maximum unseen probability, denoted $M_{\max}$ :
$M_{\max} = \max_{j: N_j = 0} p_j$
where $N_j = \sum_{i=1}^n X_{ij}$ is the count of observed occurrences for symbol $j$ . The objective is to construct a non-asymptotic, distribution-free upper confidence bound $U_n(\alpha)$ such that, with probability at least $1-\alpha$ , $M_{\max} \leq U_n(\alpha)$ . This bound serves as a stopping rule: sampling can cease once $U_n(\alpha) \leq \varepsilon$ .

Methodology and Theoretical Framework

The paper develops a unified theory across two regimes: bounded alphabets (finite, known $M$ ) and unbounded alphabets (countably infinite, subject to a summability condition $\sum p_j < \infty$ ).

1. Bounded Alphabet Regime ( $M < \infty$ )

Benchmark: The authors identify the multiplicity-adjusted "rule of three" (Bonferroni correction) as a baseline: $T_{\text{Bonf}} = \log(M/\alpha)/n$ . They note this is conservative as it assumes all $M$ categories are unseen.
Worst-Case Data-Independent Bound: Theorem 2.1 refines the Bonferroni bound using an $\ell_r$ -norm approach and Markov's inequality. By optimizing over the parameter $r$ , they derive a bound $T_{\text{wc}}(n, M, \alpha)$ that improves the non-asymptotic constant of the Bonferroni bound while remaining data-independent.
Data-Dependent Bound: Theorem 2.2 introduces a bound that adapts to the empirical incidence counts. It replaces the worst-case factor $M$ with a data-dependent effective alphabet size $m_{b_n}(\hat{p}) = \sum (1-\hat{p}_j)^{b_n}$ , where $\hat{p}_j = N_j/n$ . This quantity concentrates on unseen categories as the tuning parameter $b_n$ increases. The bound is derived using McDiarmid's inequality to control the deviation between the empirical and true sums.
Optimality: Theorem 2.3 establishes a matching lower bound, proving that no uniformly valid upper confidence bound can improve upon the order $\log(K/\alpha)/n$ , where $K$ is the number of unseen categories. This confirms the near-optimality of the proposed data-dependent bounds.

2. Unbounded Alphabet Regime ( $M = \infty$ )

Impossibility Result: Theorem 3.1 demonstrates that no non-trivial, data-independent (worst-case) upper bound can achieve valid coverage uniformly over the class of summable prevalence sequences. This is because the expectation of the relevant functionals diverges in the unbounded case.
Data-Dependent Bound: To overcome this, Theorem 3.4 proposes a fully data-dependent bound. It utilizes an $r$ -norm construction that leverages the finiteness of the total mass $S = \sum p_j$ . The procedure estimates $S$ via an unbiased estimator $\hat{S}$ and constructs an upper confidence bound $S^*$ . The bound $U_n$ is then optimized by choosing a data-dependent parameter $R^*$ that scales with $\log n$ .
Optimality: Theorem 3.5 provides a matching lower bound, showing that the rate achieved by the proposed procedure, $n^{-1}(\log n - \log \log n)$ , is essentially optimal for the unbounded regime.

3. Sequential Stopping Rules

The derived confidence intervals are utilized to construct sequential stopping rules. The procedure stops at the first sample size $n$ where the upper bound $U_n(\alpha) \leq \varepsilon$ . The authors evaluate these rules against coverage-based diagnostics and species-accumulation curves, specifically testing robustness against contamination (spurious low-prevalence categories).

Key Results and Empirical Findings

Performance in Simulations:
- In bounded settings with light-tailed distributions (where most symbols are observed), the proposed Bounded bound outperforms the standard Bonferroni benchmark.
- In heavy-tailed settings (many rare/unseen symbols), the Unbounded bound produces substantially shorter intervals than both the Bounded and Bonferroni bounds, even when the true alphabet is finite but large.
- The proposed methods achieve nominal coverage levels (typically close to 100% empirically) across all tested scenarios.
Selection Heuristic: The paper proposes a practical heuristic (Equation 10) and a visual diagnostic (accumulation curves) to guide the choice between the Bounded and Unbounded procedures. The Unbounded approach is recommended when the total probability mass is small relative to the effective alphabet size, or when the accumulation curve shows persistent growth without a clear asymptote.
Robustness: In the presence of contamination (artificial low-prevalence categories mimicking sequencing errors), the $M_{\max}$ -based stopping rules remain stable and robust. In contrast, coverage-based criteria may stop prematurely or require excessive sampling effort.
Real-World Application (TCGA): Applied to The Cancer Genome Atlas (TCGA) somatic mutation data, the Unbounded procedure was deemed appropriate due to the vast, effectively infinite nature of the genomic variant space. The method provided finite-sample guarantees for the prevalence of unseen variants, offering rigorous uncertainty quantification beyond simple expected discovery counts.

Significance and Claims

The paper claims to provide the first non-asymptotic, distribution-free analysis of confidence intervals for the maximum unseen probability in both bounded and unbounded Bernoulli product models.

Key contributions include:

Theoretical Limits: Characterizing the limits of data-independent bounds, specifically proving the impossibility of valid worst-case bounds in unbounded regimes.
Optimality: Establishing matching lower bounds that demonstrate the near-optimality of the proposed data-dependent procedures in both regimes.
Practical Utility: Offering a principled framework for sequential stopping that is robust to contamination, addressing a critical gap in existing ecological and genomic stopping rules which often rely on asymptotic assumptions or are fragile to rare artifacts.
Finite-Sample Guarantees: Providing rigorous uncertainty quantification for unobserved events, which is particularly valuable in safety-critical applications (e.g., clinical trials, reliability engineering) where observing zero events does not justify concluding zero risk.

The authors position their work as a refinement of existing "rule of three" heuristics and coverage-based diagnostics, offering tighter, data-adaptive bounds that are theoretically grounded in minimax optimality.