Weighted sampling without replacement
From MaRDI portal
Abstract: Comparing concentration properties of uniform sampling with and without replacement has a long history which can be traced back to the pioneer work of Hoeffding (1963). The goal of this short note is to extend this comparison to the case of non-uniform weights, using a coupling between the two samples. When the items' weights are arranged in the same order as their values, we show that the induced coupling for the cumulative values is a submartingale coupling. As a consequence, the powerful Chernoff-type upper-tail estimates known for sampling with replacement automatically transfer to the case of sampling without replacement. For general weights, we use the same coupling to establish a sub-Gaussian concentration inequality. We also construct another martingale coupling which allows us to answer a question raised by Luh and Pippenger (2014) on sampling in Polya urns with different replacement numbers.
Recommendations
- Concentration inequalities for sampling without replacement
- Concentration inequalities for samples without replacement
- Large-deviation bounds for sampling without replacement
- Concentration inequalities on the multislice and for sampling without replacement
- Hoeffding-Serfling inequality for U-statistics without replacement
Cites work
- A counterexample to a correlation inequality in finite sampling
- A Generalization of Sampling Without Replacement From a Finite Universe
- A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
- Asymptotic Theory for Successive Sampling with Varying Probabilities Without Replacement, I
- Comparison methods for stochastic models and risks
- Concentration inequalities for sampling without replacement
- Concentration inequalities. A nonasymptotic theory of independence
- scientific article; zbMATH DE number 3166683 (Why is no real title available?)
- scientific article; zbMATH DE number 1179517 (Why is no real title available?)
- Large-deviation bounds for sampling without replacement
- Negative association of random variables, with applications
- On the inclusion probabilities in some unequal probability sampling plans without replacement
- Probability Inequalities for Sums of Bounded Random Variables
- Probability inequalities for the sum in sampling without replacement
- Size-biased permutation of a finite sequence with independent and identically distributed terms
- Some limit theorems with applications in sampling theory
- Stochastic ordering and dependence in applied probability
- Stochastic orders
- Successive sampling in large finite populations
- The Existence of Probability Measures with Given Marginals
- The two-parameter Poisson-Dirichlet distribution derived from a stable subordinator
Cited in
(8)- A counterexample to a correlation inequality in finite sampling
- Exponential inequality for chaos based on sampling without replacement
- Large-deviation bounds for sampling without replacement
- scientific article; zbMATH DE number 4032783 (Why is no real title available?)
- Counting by Weighing: An Alternative Sampling Scheme
- Practical provably secure flooding for blockchains
- Enumerative theory for the Tsetlin library
- Exponential inequalities for sampling designs
This page was built for publication: Weighted sampling without replacement
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1668054)
