Exact PPS sampling with bounded sample size

DOI10.1016/J.IPL.2023.106382MaRDI QIDQ6161441zbMATH OpenFDO

Authors Brian Hentschel, Peter J. Haas, Yuanyuan Tian

Publication date 5 June 2023

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2105.10809

zbMATH Keywords

algorithmsprobability proportional to sizeunequal probability samplingweighted sampling

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Abstract: Probability proportional to size (PPS) sampling schemes with a target sample size aim to produce a sample comprising a specified number $n$ of items while ensuring that each item in the population appears in the sample with a probability proportional to its specified "weight" (also called its "size"). These two objectives, however, cannot always be achieved simultaneously. Existing PPS schemes prioritize control of the sample size, violating the PPS property if necessary. We provide a new PPS scheme that allows a different trade-off: our method enforces the PPS property at all times while ensuring that the sample size never exceeds the target value $n$. The sample size is exactly equal to $n$ if possible, and otherwise has maximal expected value and minimal variance. Thus we bound the sample size, thereby avoiding storage overflows and helping to control the time required for analytics over the sample, while allowing the user complete control over the sample contents. The method is both simple to implement and efficient, being a one-pass streaming algorithm with an amortized processing time of $O(1)$ per item.

Cites work

• A general purpose unequal probability sampling plan
• A general result for selecting balanced unequal probability samples from a stream
• Asymptotic Theory of Rejective Sampling with Varying Probabilities from a Finite Population
• Efficient stream sampling for variance-optimal estimation of subset sums
• Model assisted survey sampling
• On sampling with probability proportional to size
• On the Theory of Systematic Sampling, II
• Sampling with Unequal Probabilities without Replacement: A Review
• Solutions to the Problem of Unequal Probability Sampling without Replacement

This page was built for publication: Exact PPS sampling with bounded sample size

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6161441)