Sharp exponential inequalities in survey sampling: conditional Poisson sampling schemes

Patrice Bertail, Stéphan ClémençonarXiv 2016 · DOI · arXiv

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:

  1. Conditional Representation: The probability of deviation in a rejective scheme is expressed as a ratio of probabilities involving independent Bernoulli variables.
  2. 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.
  3. 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

Abstract

This paper is devoted to establishing exponential bounds for the probabilities of deviation of a sample sum from its expectation, when the variables involved in the summation are obtained by sampling in a finite population according to a rejective scheme, generalizing sampling without replacement, and by using an appropriate normalization. In contrast to Poisson sampling, classical deviation inequalities in the i.i.d. setting do not straightforwardly apply to sample sums related to rejective schemes, due to the inherent dependence structure of the sampled points. We show here how to overcome this difficulty, by combining the formulation of rejective sampling as Poisson sampling conditioned upon the sample size with the Escher transformation. In particular, the Bennett/Bernstein type bounds established highlight the effect of the asymptotic variance of the (properly standardized) sample weighted sum and are shown to be much more accurate than those based on the negative association property shared by the terms involved in the summation. Beyond its interest in itself, such a result for rejective sampling is crucial, insofar as it can be extended to many other sampling schemes, namely those that can be accurately approximated by rejective plans in the sense of the total variation distance.
BibTeX
@misc{bertail2016sharp,
  author = {Patrice Bertail and Stéphan Clémençon},
  title = {{Sharp exponential inequalities in survey sampling: conditional Poisson sampling schemes}},
  year = {2016},
  eprint = {1610.03776},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1610.03776},
}
Figure