Tighter Confidence Intervals under Without Replacement Sampling via Empirical Rate Functions

Shubhanshu Shekhar, Aaditya Ramdas · 2026

Read Tighter Confidence Intervals under Without Replacement Sampling via Empirical Rate Functions by Shubhanshu Shekhar, Aaditya Ramdas (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-14423.txt.

Introduction

Shekhar and Ramdas build tighter confidence intervals for sampling without replacement. The task is to bound a population mean from a sample drawn with no repeats. For a finite alphabet, they derive a floor on interval width from large-deviation rate functions. A new interval built from an empirical rate function meets that floor up to constants in set regimes. A dual form makes the interval cheap to compute. Extensions cover the unit interval and smooth Banach spaces.

Catalog record

CREATORShubhanshu Shekhar, Aaditya Ramdas
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE140389
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2603.14423

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Tighter Confidence Intervals under Without Replacement Sampling via Empirical Rate Functions Shubhanshu Shekhar, Aaditya Ramdas Abstract We consider the problem of constructing confidence intervals (CIs) for the population mean of N N values { x 1 , … , x N } ⊂ Σ N \{x_{1},\ldots,x_{N}\}\subset\Sigma^{N} based on a random sample of size n n , denoted by X n ≡ ( X 1 , … , X n ) X^{n}\equiv(X_{1},\ldots,X_{n}) , drawn uniformly without replacement ( WoR ). We begin by focusing on the finite alphabet ( | Σ | = k < ∞ |\Sigma|=k<\infty ) and moderate accuracy ( log ⁡ ( 1 / α N ) ≫ ( k + 1 ) ​ log ⁡ N \log(1/\alpha_{N})\gg(k+1)\log N ) regime, and derive a fundamental lower bound on the width of any level- ( 1 − α N ) (1-\alpha_{N}) CI in terms of the inverse of the WoR rate functions from the theory of large deviations. Guided by this lower bound, we propose a new level- ( 1 − α N ) (1-\alpha_{N}) CI using an empirical inverse rate function, and show that in certain asymptotic regimes the width of this CI matches the lower bound up to constants. We also derive a dual formulation of the inverse rate function that enables efficient computation of our proposed CI. We then move beyond the finite alphabet case and use a Bernoulli coupling idea to construct an almost sure CI for Σ = [ 0 , 1 ] \Sigma=[0,1] , and a conceptually simple nonasymptotic CI for the case of Σ \Sigma being a ( 2 , D ) (2,D) smooth Banach space. For both finite and general alphabets, our results employ classical large deviation techniques in novel ways, thus establishing new connections between estimation under WoR sampling and the theory of large deviations. 1 Introduction Let \mathcal{X}\equiv\mathcal{X}_{N}=\{x_{1},x_{2},\ldots,x_{N}\} denote a collection of N items lying in a support set (or alphabet) \Sigma , and define the population mean and variance associated with \mathcal{X}_{N} as \displaystyle\mu\equiv\mu_{N}=\frac{1}{N}\sum_{i=1}^{N}x_{i},\quad\text{and}\quad\sigma^{2}\equiv\sigma_{N}^{2}=\frac{1}{N}\sum_{i=1}^{N}(x_{i}-\mu_{N})^{2}. (2) For an integer n<N , let X_{1},X_{2},\ldots,X_{n} denote n observations drawn uniformly without replacement ( WoR ) from \mathcal{X}_{N} ; that is, X_{1}\sim\mathrm{Uniform}(\mathcal{X}_{N}),\quad\text{and}\quad X_{i}\sim\mathrm{Uniform}(\mathcal{X}_{N}\setminus\{X_{1},\ldots,X_{i-1}\}),\;\text{for }i\geq 2. Given these observations and a confidence parameter \alpha\in(0,1] , our goal is to construct a level- (1-\alpha) confidence interval (CI) for the unknown population mean. Formally, we want to construct a subset C_{n}\equiv C_{n}(X_{1},\ldots,X_{n},\alpha) , such that \mathbb{P}\left(\mu_{N}\in C_{n}\right)\geq 1-\alpha , for each fixed n . Note that the only source of randomness in the above expression is due to the sampling scheme; the elements \{x_{1},\ldots,x_{N}\} are themselves nonrandom quantities. Our first goal in this paper is to understand the fundamental instance-dependent limits on the width achievable by any level- (1-\alpha) CI. Focusing on the finite alphabet case (i.e., \Sigma\subset[0,1],|\Sigma|<\infty ), we derive a new information-theoretic lower bound on the width of any level- (1-\alpha) CI in Theorem 3.4 , and then build upon this result to propose a new CI in Section 3.2 . Both the lower and upper bounds depend on the WoR large deviation rate function terms, and in Theorem 3.9 , we show that in certain regimes (that we refer to as moderate accuracy regimes; see Definition 3.3 ) the width of our proposed CI nearly matches the lower bound modulo constants (see Remark 3.10 for a more precise discussion). Next, in Theorem 3.11 , we derive a dual representation of these inverse rate function terms that makes their evaluation computationally feasible. These results employ elementary type-counting arguments that rely crucially on the finiteness of \Sigma . To handle the case of continuous alphabets, such as \Sigma=[0,1] or when \Sigma is a smooth Banach space, we use a Bernoulli coupling identity to construct improved CIs with strong theoretical and empirical performance. The construction of tight CIs for the population mean under WoR sampling is a fundamental problem that arises in many important applications. Some typical examples include risk-limiting audits ( 15 ) , survey sampling ( 4 ) , subsampled Markov chain Monte Carlo (MCMC) methods for scalable Bayesian inference ( 1 ) , and large-scale kernel embedding ( 19 ) . In Section 3.3.2 , we further explore the kernel mean embedding application and empirically compare our proposed CI for smooth Banach spaces with that of 19 . 2 Preliminaries Let \mathcal{X}_{N}=\{x_{1},\ldots,x_{N}\} denote a collection of N items x_{i}\in\Sigma for all i\in[N]\coloneqq\{1,\ldots,N\} , with population mean and variance denoted by \mu_{N} and \sigma_{N}^{2} . Let X^{n}=(X_{1},\ldots,X_{n}) denote a WoR sample from the set \mathcal{X}_{N} of size n . Denote the fraction n/N by \beta_{N} , and let \bar{\beta}_{N} denote 1-\beta_{N} . The subscripts N are there to denote an implicit triangular array setup; whenever there is no confusion, we will drop the subscripts and simply use \mathcal{X},\mu,\sigma^{2} , \beta and \bar{\beta} , respectively. Given the WoR sample X^{n} , we can construct the empirical distribution over the alphabet \Sigma as \widehat{P}_{n}\equiv\widehat{P}(X^{n})=\frac{1}{n}\sum_{i=1}^{n}\delta_{X_{i}} , where \delta_{X_{i}} denotes the point mass at X_{i} . Many results of this paper rely on the following fundamental coupling identity that relates WoR sampling distribution \widehat{P}_{n} to a simpler i.i.d. “Bernoulli Sampling” construction ( 12 , § 2) . Fact 2.1 (Key Coupling Identity) . Suppose \Sigma denotes an arbitrary alphabet, and let X^{n}=(X_{1},\ldots,X_{n}) denote a WoR sample from a finite population \mathcal{X}=\{x_{1},\ldots,x_{N}\} with each x_{i}\in\Sigma . Now, let J_{1},\ldots,J_{N} denote N i.i.d. \mathrm{Bernoulli}(\beta) random variables, where \beta=n/N . Let \widehat{P}_{n}\equiv\widehat{P}(X^{n})=\frac{1}{n}\sum_{i=1}^{n}\delta_{X_{i}} and \widehat{P}_{N,J}=\frac{1}{n}\sum_{i=1}^{N}J_{i}\delta_{x_{i}} denote the empirical measures associated with X^{n} and J^{N} . Then, we have \widehat{P}_{n}\;=_{d}\;\widehat{P}_{N,J}\mid\{S_{N,J}=n\} , where =_{d} indicates equality in distribution or law, and S_{N,J}\coloneqq\sum_{i=1}^{N}J_{i} . This identity allows us to employ the standard concentration techniques for independent data to study the behavior of WoR samples for general alphabets, and we illustrate its utility in Section 3.3 by developing new CIs when \Sigma is [0,1] or a smooth Banach space. For finite alphabets, this identity yields a more directly applicable finite-sample approximation result that we discuss next. In the finite-alphabet setting (when \Sigma=\{s_{1},\ldots,s_{k}\}\subset[0,1] ), the empirical distributions are also referred to as “types”, following 7 ; 9 . Let \mathcal{T}_{n}\equiv\mathcal{T}_{n}(\Sigma) denote the set of all possible distinct types based on n observations from a finite \Sigma ; that is, \displaystyle\mathcal{T}_{n}(\Sigma)=\left\{t:t=\widehat{P}(x^{n})\;\text{for some }x^{n}\in\Sigma^{n}\right\},\quad\text{where}\quad\widehat{P}(x^{n})=\frac{1}{n}\sum_{i=1}^{n}\delta_{x_{i}}. (3) It is easy to verify that |\mathcal{T}_{n}|=\binom{n+k-1}{k-1}\leq(n+1)^{k} ; see 6 . For any type t\in\mathcal{T}_{n} , let S_{t}=\{x^{n}\in\Sigma^{n}:\widehat{P}(x^{n})=t\} denote the “type-class” of t ; the collection of length- n sequences in \Sigma whose type is equal to t . Using Stirling’s approximation, we can then obtain the following bound, which we will use often in Section 3.1 and Section 3.2 . Fact 2.2 (Lemma 2.1.33 of 9 ) . Let t denote any type in \mathcal{T}_{n}(\Sigma) , and let \mathcal{X}=\{x_{1},\ldots,x_{N}\} denote a collection of N elements (with possible repetition) from \Sigma . Let \widehat{P}_{N}\equiv\widehat{P}(\mathcal{X})=\frac{1}{N}\sum_{i=1}^{N}\delta_{x_{i}} denote the type or empirical distribution associated with \mathcal{X} . Suppose X^{n}=(X_{1},\ldots,X_{n}) denotes a WoR sample from \mathcal{X} , and denote its type by \widehat{P}_{n}\equiv\widehat{P}(X^{n})=\frac{1}{n}\sum_{i=1}^{n}\delta_{X_{i}} . Then we have \displaystyle\left\lvert\frac{1}{n}\log\left(\mathbb{P}\left(\widehat{P}_{n}=t\right)\right)+I\left(t,\frac{n}{N},\widehat{P}_{N}\right)\right\rvert\leq 2\left(|\Sigma|+1\right)\left(\frac{\log(N+1)}{n}\right), (4) where I(P,\beta,Q)\coloneqq d_{\text{KL}}(P\parallel Q)+\frac{1-\beta}{\beta}d_{\text{KL}}\left(\frac{Q-\beta P}{1-\beta}\parallel Q\right), with d_{\text{KL}}(P\parallel Q)=\sum_{s\in\Sigma}P(s)\log P(s)/Q(s) for P\ll Q denoting the relative entropy (or KL divergence) between the two discrete distributions P and Q over \Sigma . This definition is valid under the

Read the complete text