📊 statistics

Tighter Confidence Intervals under Without Replacement Sampling via Empirical Rate Functions

This paper derives fundamental lower bounds on the width of confidence intervals for population means under without-replacement sampling using large deviation rate functions, and proposes new, nearly optimal confidence interval constructions for both finite and general alphabets that leverage these bounds and novel coupling techniques.

Original authors: Shubhanshu Shekhar, Aaditya Ramdas

Published 2026-03-17

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Shubhanshu Shekhar, Aaditya Ramdas

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 guess the average height of every person in a massive city (the Population). You can't measure everyone; that would take forever. Instead, you go out and measure a smaller group of people (the Sample).

In most statistics classes, you learn how to guess the average if you pick people randomly and put them back in the crowd after measuring them (like drawing names from a hat and putting the name back). This is called Sampling With Replacement.

But in the real world, you usually don't put people back. Once you measure a person, you move on to the next. This is Sampling Without Replacement (WoR). The paper by Shekhar and Ramdas tackles a specific problem: How can we make our "guessing range" (Confidence Interval) as tight and accurate as possible when we are sampling without replacement?

Here is the breakdown of their breakthrough, explained through simple analogies.

1. The Problem: The "Loose Net"

When you try to guess the city's average height, you give a range: "I'm 95% sure the average is between 5'6" and 6'0"."

Old Methods: The existing tools (like the Hoeffding or Bernstein inequalities) are like fishing with a very loose net. They guarantee you catch the fish (the true average), but the net is so wide it might include fish that are clearly too small or too big. They don't realize that as you catch more fish, the pool of remaining fish gets smaller, making your job easier.
The Goal: The authors wanted to shrink that net. They wanted the tightest possible net that still guarantees they catch the true average.

2. The Secret Weapon: The "Bernoulli Coupling"

The authors use a clever mathematical trick called a Bernoulli Coupling.

The Analogy: Imagine you have a bag of marbles.
- Scenario A (Real Life): You pull marbles out one by one and don't put them back.
- Scenario B (The Trick): Imagine you have a magical machine that decides for every single marble in the bag whether to "keep it" or "discard it" based on a coin flip. If the coin flip says "keep," you keep it.
The Magic: The authors proved that if you condition this magical machine to keep exactly the same number of marbles you pulled in Scenario A, the two scenarios become statistically identical.
Why it helps: Scenario B (the coin flips) is much easier to analyze mathematically because the decisions are independent. By translating the hard "Without Replacement" problem into the easier "Coin Flip" problem, they could use powerful existing math tools to solve the hard problem.

3. The Finite Alphabet: The "Type" Game

First, they looked at a world where the data is limited (e.g., people's heights are only measured in whole inches: 58, 59, 60...).

The "Type" Concept: Instead of caring about the order you met the people (Alice then Bob vs. Bob then Alice), they only care about the count (3 people are 58", 5 are 59", etc.). In math, this is called the "Type."
The Rate Function: They discovered that the "tightness" of your net depends on a specific mathematical curve called a Rate Function. Think of this as a "difficulty meter."
- If your sample looks very different from the whole city, the "difficulty meter" goes up, and your net gets wider.
- If your sample looks very similar to the city, the meter goes down, and your net shrinks.
The Result: They derived a Lower Bound. This is a theoretical "floor." They proved that no matter how smart you are, you cannot make your net narrower than this floor without risking a wrong guess. Then, they built a new method that hits this floor almost perfectly.

4. The Continuous World: The "Smooth Banach Space"

Real life isn't just whole inches; heights are continuous (5'6.432"). The math gets messy here.

The Smooth Banach Space: This is a fancy math term for a space where things are "smooth" and predictable (like a curved surface rather than a jagged mountain).
The Application: They applied their "Coin Flip" trick to this complex world. They created a new rule for these smooth spaces that is tighter (narrower) than the previous best rules used by experts (like Schneider, 2016).
Real World Test: They tested this on MNIST (a famous dataset of handwritten digits). They treated the images as points in a complex space and tried to guess the "average image." Their new method gave a much tighter, more accurate range than the old methods.

5. The "Almost Sure" Confidence

Finally, they tackled a philosophical question: "What if we keep taking bigger and bigger samples forever?"

The Old Way: Some methods guarantee you are right most of the time (e.g., 95% of the time), but they might be wrong occasionally, even as you get more data.
The New Way: They built an "Almost Sure" interval.
- Analogy: Imagine a safety harness. The old harness might slip once in a blue moon. The new harness is designed so that if you keep climbing, the probability of it ever slipping becomes zero. Eventually, it locks in perfectly.

Summary: Why Should You Care?

This paper is like upgrading the GPS in your car.

Before: The GPS said, "You are somewhere in this huge neighborhood."
After: The authors used a clever mathematical shortcut (the coin flip trick) to calculate a much more precise route. Now the GPS says, "You are exactly on this street."

They didn't just guess; they proved that their new method is the best possible (mathematically optimal) for certain situations and provided a practical way to calculate it. This is huge for fields like risk auditing (checking if a bank is honest), survey sampling (polling voters), and AI (making sure machine learning models are accurate without checking every single data point).

1. Problem Statement

The paper addresses the problem of constructing confidence intervals (CIs) for the population mean $\mu_N$ of a finite population $X_N = \{x_1, \dots, x_N\} \subset \Sigma$ , based on a sample $X_n = (X_1, \dots, X_n)$ drawn uniformly without replacement (WoR).

Context: Unlike independent and identically distributed (i.i.d.) sampling, WoR sampling exhibits a unique property: uncertainty vanishes as the sample size $n$ approaches the population size $N$ (i.e., when the sampling fraction $\beta = n/N \to 1$ ).
Limitation of Existing Methods:
- Hoeffding-Serfling: Classical bounds (e.g., Hoeffding 1963, Serfling 1974) often fail to capture the vanishing uncertainty as $n \to N$ or are overly conservative.
- Variance-Adaptive Methods: While methods like Bernstein-Serfling exist, they often rely on prior knowledge of variance or yield wider intervals than theoretically necessary.
- Gap: There was no fundamental understanding of the optimal width achievable for WoR sampling, nor a method that achieves this limit while being computationally feasible for general alphabets.

2. Core Methodology

The authors employ a combination of Large Deviation Theory (LDT) and a Bernoulli Coupling Identity to derive new bounds and constructions.

A. The Bernoulli Coupling Identity (Fact 2.1)

The central technical tool is a coupling between WoR sampling and i.i.d. Bernoulli sampling.

Let $J_1, \dots, J_N$ be i.i.d. $\text{Bernoulli}(\beta)$ variables where $\beta = n/N$ .
The empirical distribution of the WoR sample, $\hat{P}_n$ , is equal in distribution to the empirical distribution of the Bernoulli sample, $\hat{P}_{N,J}$ , conditioned on the sum of Bernoulli variables being exactly $n$ ( $S_{N,J} = n$ ).
Utility: This allows the authors to leverage standard concentration inequalities for independent data (which are often tighter or easier to analyze) and bound the WoR probability by a factor of roughly $1/\sqrt{n}$ (via Stirling's approximation).

B. Large Deviation Rate Functions

For finite alphabets, the authors define specific WoR rate functions ( $J_+$ and $J_-$ ) based on a generalized Kullback-Leibler (KL) divergence term $I(P, \beta, Q)$ :
$I(P, \beta, Q) = D_{KL}(P \| Q) + \frac{1-\beta}{\beta} D_{KL}\left(\frac{Q-\beta P}{1-\beta} \bigg\| Q\right)$
This term $I$ plays the role of relative entropy for WoR sampling. The rate functions $J_\pm$ represent the minimum "cost" (in terms of $I$ ) to shift the mean of a distribution $Q$ away from the population mean $P$ while satisfying the WoR constraints.

3. Key Contributions and Results

A. Fundamental Lower Bound (Finite Alphabet)

Theorem 3.4: The authors derive a fundamental information-theoretic lower bound on the width of any level- $(1-\alpha)$ CI in the "moderate accuracy" regime (where $\log(1/\alpha)$ grows faster than the alphabet size).
Result: The width of any valid CI is lower-bounded by the inverse of the WoR rate functions:
$\text{Width} \gtrsim \frac{1}{2} \left( g_+^{-1}\left(\frac{\log(1/\alpha)}{n}\right) - g_-^{-1}\left(\frac{\log(1/\alpha)}{n}\right) \right)$
where $g_\pm$ are the population inverse rate functions. This establishes that the inverse rate function is the correct complexity measure for optimal CI width.

B. Proposed Near-Optimal CI (Finite Alphabet)

Definition 3.6 & Theorem 3.7: They propose a new CI constructed by replacing the unknown population distribution in the rate functions with the empirical distribution $\hat{P}_n$ .
Near-Optimality (Theorem 3.9): They prove that the width of this proposed CI matches the lower bound up to constant factors in the moderate accuracy regime.
Computational Efficiency (Theorem 3.11): Directly computing the rate functions involves optimizing over a high-dimensional probability simplex (complexity grows with alphabet size $k$ ). The authors derive a dual formulation that reduces this to a 2-dimensional convex optimization problem, making the method computationally tractable regardless of the alphabet size.

C. Extensions to General Alphabets

Recognizing that finite alphabet assumptions limit practical utility, the authors use the Bernoulli coupling to extend results to continuous domains:

Almost Sure CI for $\Sigma = [0, 1]$ (Section 3.3.1):
- Constructs an "almost sure" CI (Naaman, 2016) that guarantees the population mean is covered for all sufficiently large $N$ with probability 1.
- Advantage: It sits between non-asymptotic bounds (like Serfling-Hoeffding) and asymptotic CLT bounds. It does not require prior knowledge of the range $[0,1]$ and offers stronger coverage guarantees than CLT-based intervals (which can fail infinitely often).
CI for Smooth Banach Spaces (Section 3.3.2):
- Extends the approach to $(2, D)$ -smooth Banach spaces (e.g., Hilbert spaces, RKHS).
- Comparison: They derive a CI that is strictly tighter than the existing state-of-the-art by Schneider (2016).
- Application: Demonstrated on Kernel Mean Embeddings using MNIST data, showing significant improvement in deviation bounds compared to Schneider's method.

4. Significance and Impact

Theoretical Breakthrough: The paper establishes the first fundamental lower bound for WoR CI widths, proving that existing methods (like Hoeffding-Serfling) are suboptimal and that the proposed rate-function-based approach is nearly optimal.
Computational Tractability: By providing a dual formulation, the authors solve the computational bottleneck of evaluating large deviation rate functions, making the theoretically optimal CI practical for high-dimensional data.
Practical Utility: The extension to Banach spaces and the "almost sure" CI for $[0,1]$ $[0, 1]$ provide immediate tools for modern applications like:
- Risk-Limiting Audits: Where finite population correction is critical.
- Scalable Bayesian Inference: Subsampled MCMC methods.
- Kernel Methods: Tighter bounds for kernel mean embeddings in machine learning.
Unifying Framework: The paper unifies estimation under WoR sampling with large deviation theory, demonstrating that the Bernoulli coupling is a powerful device for transferring results from independent settings to dependent (WoR) settings.

5. Conclusion

Shekhar and Ramdas successfully bridge the gap between theoretical limits and practical construction for confidence intervals in without-replacement sampling. They prove that the inverse of the WoR rate function characterizes the optimal width, propose a computationally efficient estimator that achieves this, and generalize the framework to continuous and Banach space settings, outperforming existing benchmarks in both theory and empirical experiments.