The Exceedance Design Effect: Effective Sample Size for Thresholds under Clustering
Adam Noonan
stat.ML
Aug 21, 2026 · v2
cs.LG
TL;DR
The paper's central limit theorem, propositions, finite-sample counterexample and variance-estimator consistency are machine-checked in a 59-file Lean 4 and Mathlib proof bundle.
Abstract
Suppose we want a cutoff that 90% of a population falls below. We estimate it from a sample, and another sample would give a different cutoff and a different fraction below it. We ask how much that fraction varies when observations come in independent groups, such as pupils in classrooms or sentences in news articles. We prove that grouping multiplies its large-sample variance by $1+(m-1)ρ_I(p)$, where $m$ is the group size, $p$ is the target fraction, and $ρ_I(p)$ measures whether two members of a group fall on the same side of the cutoff. That correlation can differ from the correlation between the scores themselves, and it changes with the target. We give a direct proof, a counterexample to using score correlation, and an extension to unequal group sizes. A dataset therefore does not have one effective sample size. How much information it contains depends on the question you ask. In our document experiment, the same 1,000 rows carried about 217 independent observations' worth of information at the median. At the 95th percentile, they carried about 621. Nothing about the dataset changed. We asked it a different question. The number of rows is a property of the dataset. The effective sample size belongs to the analysis.
Problem
A cutoff estimated as a sample quantile has random population coverage. The question is how that coverage variance behaves when reference observations come in independent clusters, and whether score correlation is the right quantity for an effective sample size.
Approach
The authors prove a large-sample normal limit for calibration-conditional coverage under iid exchangeable clusters with a continuous marginal. The variance is inflated by the exceedance design effect 1+(m-1)ρ_I(p), where ρ_I(p) is the within-cluster correlation of threshold indicators. The results are extended to bounded unequal cluster sizes and paired with a consistent count-based variance estimator. Theorem 1, the propositions, the counterexample and the estimator's consistency are verified in Lean 4 with Mathlib.
Results
Score correlation can understate or overstate coverage variance. A zero-score-correlation example has design effect 13/9 at p=0.9. Effective sample size depends on the target level: in a document dataset, 1,000 rows were worth about 217 independent observations at the median and about 621 at the 95th percentile.
| Mixture weight q | Score corr ρ | Indicator corr ρ_I(0.9) | Indicator design effect | Score-based substitute |
|---|
| 0.75 | 0.50 | 0.7222 | 1.7222 | 1.50 |
| 0.50 | 0.00 | 0.4444 | 1.4444 | 1.00 |
| 0.30 | -0.40 | 0.2222 | 1.2222 | 0.60 |
Zero-correlation counterexample at p=0.9