Statistical Inference for Sampling Without Replacement

This direction is split into other directions: finite population sampling, finite-population concentration inequalities. Its last version stays readable and citable here.

Version 1 of 146 papers85 conceptsfrozen 2026-10-04

In standard machine learning theory, we often rely on a convenient fiction: the assumption that data points are independent and identically distributed (i.i.d.). This assumes we are sampling "with replacement" from an infinite distribution, where picking one data point has no effect on the next.

In practice, we almost always sample without replacement (WoR). We shuffle a finite dataset and iterate through it, or we partition a fixed pool of data into training and test sets. While this might seem like a minor implementation detail, it introduces complex statistical dependencies: every item we select depletes the remaining pool, changing the probabilities for all subsequent selections.

A growing body of research demonstrates that by explicitly modeling these dependencies—rather than ignoring them—we can derive significantly tighter error bounds, faster algorithms, and more robust statistical tests.

The Intuition of Depletion

The fundamental difference between sampling with and without replacement is how uncertainty behaves as we collect more data.

In an infinite population (sampling with replacement), our uncertainty about the mean decreases at a rate of $1/\sqrt{n}$. However, in a finite population of size $N$, our uncertainty must eventually reach zero when $n = N$. Standard i.i.d. bounds, like the Hoeffding inequality, are "pessimistic" because they don't account for this. They assume that even after seeing 99% of the data, the last 1% is still a total mystery.

To fix this, researchers like Markus Schneider and Aaditya Ramdas utilize finite population correction factors. By employing the Hypergeometric distribution instead of the Binomial, or the Serfling inequality instead of Hoeffding, they integrate a mechanism where the "safety net" of the bound shrinks as the sample size approaches the population size. As Byung-Cheol Shin notes in the context of high-stakes quality testing, this prevents "over-testing" by recognizing that uncertainty regarding the remaining items vanishes as more units are destroyed and inspected.

Transductive Learning: Exploiting the Unlabeled

The most prominent application of this logic is in transductive learning. Unlike inductive learning, which seeks a general rule for any future data, transductive learning aims to predict labels for a specific, known set of unlabeled points.

Because the training and test sets are simply two partitions of a single, fixed pool, they are inherently coupled. Ran El-Yaniv, Philip Derbeko, and Ron Meir showed that this coupling allows for the construction of data-dependent priors. In their work on Explicit Learning Curves for Transduction, they derived PAC-Bayesian bounds that are much tighter than traditional "black box" bounds because they leverage the fact that the unlabeled test points are known in advance.

More recently, Yingzhen Yang resolved long-standing theoretical gaps by introducing Transductive Local Complexity. By using an exponential version of the Efron-Stein inequality designed for WoR sampling, Yang proved that transductive learning can achieve the same "fast rates" of convergence as inductive learning, despite the lack of independence between samples.

Anytime-Valid Confidence Sequences

Traditional confidence intervals are valid only if you decide the sample size before you start. If you stop early because the results look good, you risk "p-hacking."

Ian Waudby-Smith and Aaditya Ramdas addressed this by developing confidence sequences for sampling without replacement. These are "anytime-valid" bounds that allow a researcher to monitor a stream of data and stop at any moment.

Their approach uses a "betting" framework: if you can't make money betting against a null hypothesis, that hypothesis is likely true. By incorporating the constraints of a finite population, these sequences are strictly tighter than those for sampling with replacement. They provide a mathematical guarantee that the interval will shrink to exactly zero width the moment the last item in the population is sampled.

Beyond Theory: Physical and Computational Constraints

The shift from infinite-pool approximations to finite-population reality has immediate practical consequences in fields where data is scarce or expensive:

  • Genomics: In single-cell RNA sequencing, we only capture a fraction of the molecules in a cell. Liam Hodgson and Danilo Bzdok developed HyperCell, which uses the Hypergeometric distribution to recover absolute molecular counts. By modeling the measurement as sampling without replacement, they can distinguish between "true zeros" (the gene isn't there) and "technical dropouts" (we just didn't catch it).
  • Computer Vision: For decades, the RANSAC algorithm used a flawed stopping criterion based on independent sampling. Johannes L. Schönberger and colleagues showed that by replacing this with an exact WoR calculation, they could prevent "catastrophic early stopping" in complex image matching tasks.
  • Databases: When estimating the size of a query result (cardinality estimation), Beibin Li proved that sampling without replacement provides significantly better accuracy than sampling with replacement, allowing database engines to generate more efficient execution plans with smaller samples.

Summary

The move toward sampling without replacement represents a shift from "idealized" statistics to "constrained" statistics. By acknowledging that our data pools are finite and that our selections are dependent, we move away from loose, pessimistic approximations and toward sharp, precise guarantees that reflect the physical reality of the data-gathering process.

Papers in this version

History & citationVersion 1 · 2026-10-04

Split into other directions · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_statistical_inference_for_sampling_witho_cd51b182,
  title = {Statistical Inference for Sampling Without Replacement},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/statistical-inference-for-sampling-without-replacement/rdr_cd51b182142d4be1899e4fe4ef141c70},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-21},
}

This exact version (version 1, frozen text):

@misc{lacuna_statistical_inference_for_sampling_witho_cd51b182_v1,
  title = {Statistical Inference for Sampling Without Replacement},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/statistical-inference-for-sampling-without-replacement/rdr_cd51b182142d4be1899e4fe4ef141c70/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-21},
}