Confidence sequences for sampling without replacement

Code

• github.com/wannabesmith/confseq_wor
  OfficialIn papernone★ 4
• github.com/gostevehoward/confseq
  none★ 78
• github.com/wannabesmith/confseq
  none★ 1

Abstract

Many practical tasks involve sampling sequentially without replacement (WoR) from a finite population of size N, in an attempt to estimate some parameter ^. 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 ^. A CS is a sequence of confidence sets (C_n)_n=1^N, that shrink in size, and all contain ^ 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.

Reproductions