Abstract
This paper establishes sharp exponential bounds for the probabilities of deviation of a sample sum from its expectation under rejective sampling schemes. Rejective sampling generalizes sampling without replacement by conditioning independent Poisson trials on a fixed sample size. Unlike standard Poisson sampling, the inherent dependence structure in rejective schemes prevents the direct application of classical i.i.d. deviation inequalities. By combining the conditional representation of rejective sampling with the Escher transformation and local limit theorems, the authors derive Bennett- and Bernstein-type bounds that explicitly incorporate the reduced asymptotic variance of the estimator. These results are shown to be significantly more accurate than those based on negative association and can be extended to other sampling designs that are close to rejective plans in total variation distance.
Introduction
In survey statistics, the Horvitz-Thompson estimator is a fundamental tool for estimating population totals. To assess the reliability of these estimates, researchers rely on concentration inequalities—mathematical bounds that limit the probability that an estimate deviates significantly from its true value.
While independent sampling designs (like Poisson sampling) allow for the use of standard tools such as the Bernstein inequality, practical surveys often utilize fixed-size designs. Rejective sampling, which generalizes simple sampling without replacement (SWOR), is a primary example. These designs introduce a dependence structure: selecting one unit slightly alters the selection probability of others to maintain a constant total sample size. This dependence makes standard i.i.d. inequalities either inapplicable or overly conservative, as they fail to account for the variance reduction inherent in fixed-size sampling.
The Methodological Framework
The authors overcome the challenges of dependence by treating rejective sampling as a Poisson sampling scheme conditioned on the event that the total sample size equals a fixed number $n$. Their derivation follows a rigorous three-step theoretical framework:
- Conditional Representation: The probability of deviation in a rejective scheme is expressed as a ratio of probabilities involving independent Bernoulli variables.
- Escher Transformation: To analyze the numerator of this ratio, the authors apply an exponential change of measure (the Escher transformation). This technique, common in large deviation theory, "shifts" the distribution to make the rare tail event of interest appear more likely, allowing for a more precise estimation of its probability.
- Local Limit Theorems: To handle the denominator—the probability that a sum of independent Bernoulli variables exactly equals its mean—the authors employ a local Berry-Esseen bound. This ensures that the resulting bound is not just valid, but "sharp."
Key Insights: From Poisson to Asymptotic Variance
The central breakthrough of this work is the "Variance Reduction" insight. Previous attempts to bound errors in rejective sampling often relied on the property of "negative association." While valid, these bounds typically used the variance associated with a standard Poisson scheme.
However, fixed-size sampling is inherently more stable than Poisson sampling. This paper demonstrates that a truly sharp bound must involve the asymptotic variance (denoted as $\sigma^2_N$), which is smaller than the Poisson variance. By canceling out problematic terms through their conditional approach, the authors produce bounds that reflect the actual, reduced variability of the survey design.
Principal Results
Theorem 4: Sharp Bennett and Bernstein Bounds
Theorem 4 serves as the centerpiece of the paper, establishing Bennett- and Bernstein-type bounds for the Horvitz-Thompson estimator under rejective sampling. These bounds are "sharp" in the sense that they are optimized for the specific variance structure of the rejective design, providing much tighter error estimates than previous benchmarks.
Theorem 5: Handling Estimation Bias
In practice, using Poisson parameters to estimate a total in a rejective scheme can introduce a slight bias. Theorem 5 extends the results of Theorem 4 to provide practical tail bounds for the standard Horvitz-Thompson estimator, accounting for this bias and ensuring the bounds remain robust in real-world applications.
Universality and SWOR
While the focus is on rejective sampling, the authors demonstrate the universality of their approach. Lemma 3 shows that these inequalities can be extended to any sampling scheme that is "close" to a rejective plan in terms of Total Variation (TV) distance or Kullback-Leibler divergence, such as Rao-Sampford or Pareto sampling. Furthermore, for the specific case of Sampling Without Replacement (SWOR), the proposed bounds outperform existing benchmarks by more gracefully handling scenarios where the sample size $n$ is a large fraction of the population size $N$.
Limitations and Future Directions
The derived bounds are subject to certain asymptotic requirements. Specifically, the universal constants $C$ and $D$ in the theorems are valid only when the variance of the sample size ($d_N$) in the underlying Poisson scheme is sufficiently large. In cases of very small populations or extremely skewed designs, these bounds may not yet be applicable.
Additionally, while the theoretical bounds are sharp, calculating the exact inclusion probabilities ($\pi_i$) for rejective sampling remains computationally intensive. Future research may focus on extending these sharp inequalities to more complex, non-linear statistics, such as regression coefficients or ratios, which are frequently used in complex survey analysis.
Summary updated