# Confidence sequences for sampling without replacement

arXiv: https://arxiv.org/abs/2006.04347 · HTML: https://mlsanity.com/paper/2006.04347/

## Key facts

- Cited by 23 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Jun 2020.

## Built on by (most cited first, 23 of 23)

- [Anytime-valid off-policy inference for contextual bandits](https://mlsanity.com/paper/2210.10768/) (2022)
- [Time-uniform central limit theory and asymptotic confidence sequences](https://mlsanity.com/paper/2103.06476/) (2021)
- [A General Framework for Data-Use Auditing of ML Models](https://mlsanity.com/paper/2407.15100/) (2024)
- [Online multiple testing with e-values](https://mlsanity.com/paper/2311.06412/) (2023)
- [On the near-optimality of betting confidence sets for bounded means](https://mlsanity.com/paper/2310.01547/) (2023)
- [Nonparametric extensions of randomized response for private confidence sets](https://mlsanity.com/paper/2202.08728/) (2022)
- [Risk-limiting Financial Audits via Weighted Sampling without Replacement](https://mlsanity.com/paper/2305.06884/) (2023)
- [Early-Exit Neural Networks with Nested Prediction Sets](https://mlsanity.com/paper/2311.05931/) (2023)
- [On the Provable Performance Guarantee of Efficient Reasoning Models](https://mlsanity.com/paper/2510.09133/) (2025)
- [PAC Mode Estimation using PPR Martingale Confidence Sequences](https://mlsanity.com/paper/2109.05047/) (2021)
- [Improved Offline Contextual Bandits with Second-Order Bounds: Betting and Freezing](https://mlsanity.com/paper/2502.10826/) (2025)
- [Instance-Level Data-Use Auditing of Visual ML Models](https://mlsanity.com/paper/2503.22413/) (2025)
- [The extended Ville's inequality for nonintegrable nonnegative supermartingales](https://mlsanity.com/paper/2304.01163/) (2023)
- [Rank Confidence Sequences:Anytime-valid Leaderboards](https://mlsanity.com/paper/2609.32211/) (2026)
- [PICProp: Physics-Informed Confidence Propagation for Uncertainty Quantification](https://mlsanity.com/paper/2310.06923/) (2023)
- [Concentration Inequalities for Exchangeable Tensors and Matrix-valued Data](https://mlsanity.com/paper/2601.20152/) (2026)
- [Identifying Copeland Winners in Dueling Bandits with Indifferences](https://mlsanity.com/paper/2310.00750/) (2023)
- [Positive Semidefinite Matrix Supermartingales](https://mlsanity.com/paper/2401.15567/) (2024)
- [Estimating Unknown Population Sizes Using the Hypergeometric Distribution](https://mlsanity.com/paper/2402.14220/) (2024)
- [ALIVE: Warnings Before Exclusion in Budgeted Multi-Source Learning](https://mlsanity.com/paper/2607.29400/) (2026)
- [Discovering Translation-Worthy Languages with E-Values](https://mlsanity.com/paper/2609.06593/) (2026)
- [Sharp Limits for Honest Uncertainty in Hard-Budget Repeated Evaluation](https://mlsanity.com/paper/2609.29140/) (2026)
- [When Can Old Evaluations Certify a New Model? Label-Efficient Release Decisions under Evaluator Drift](https://mlsanity.com/paper/2609.32267/) (2026)

## Abstract (arXiv)

Many practical tasks involve sampling sequentially without replacement (WoR) from a finite population of size N, in an attempt to estimate some parameter θ^star. Accurately quantifying uncertainty throughout this process is a nontrivial task, but is necessary because it often determines when we stop collecting samples and confidently report a result. We present a suite of tools for designing confidence sequences (CS) for θ^star. A CS is a sequence of confidence sets (Cn)n=1N, that shrink in size, and all contain θ^star simultaneously with high probability. We present a generic approach to constructing a frequentist CS using Bayesian tools, based on the fact that the ratio of a prior to the posterior at the ground truth is a martingale. We then present Hoeffding- and empirical-Bernstein-type time-uniform CSs and fixed-time confidence intervals for sampling WoR, which improve on previous bounds in the literature and explicitly quantify the benefit of WoR sampling.