On inclusion probabilities for weighted random sampling without replacement

Year 2024, Volume: 42 Issue: 6, 1780 - 1785, 09.12.2024

Murat Güngör

Abstract

Hajj is an annual Islamic pilgrimage to Mecca, Saudi Arabia. It is performed on certain dates of the lunar year. The Saudi government sets quotas for various countries to keep the pilgrims’ number at a manageable level. While some countries maintain waiting lists and evaluate applications on a first-come-first-served basis, others conduct draws to determine who will be admitted to the journey. Türkiye is one of the latter, where candidates’ odds are, in a sense, proportional to the square of the number of years they have been waiting for, or to be more accurate, to the square of the number of times they made an application. This policy, which is called “katsayılı kura sistemi” in Turkish, is adopted by countries like Bosnia and Herzegovina and Belgium as well. The sampling process described above is referred to as “weighted random sampling without replacement with defined weights” (WRS) in the literature. The purpose of this paper is to investigate the inclusion probabilities in WRS for which no efficient method exists. First, we take up an analytical approach and derive theoretical lower and upper bounds on the inclusion probabilities. Second, for situations where these bounds are not as tight as desired, we propose an estimation procedure by simulation. The simulation design is based on an ingenious idea from computer science. We apply our results to estimate applicants’ chances in Türkiye’s last hajj draw before the COVID-19 pandemic. It turns out that one who participates in the draws for the first time has a chance in between 0.12% and 0.13%; similar bounds for one who participates for the eleventh time (for one with the largest number of applications) are 13.22% and 14.16%. These bounds actually rely on a conjecture relating WRS to a more general problem for which we provide a supportive example.

Keywords

Hajj Draws, Inclusion Probabilities, Weighted Random Sampling, Without Replacement

References

• REFERENCES [1] Efraimidis PS. Weighted random sampling over data streams. In Zaroliagis C, Pantziou G, Kontogiannis S (Eds.). Algorithms, Probability, Networks, and Games, vol. 9295, 2015. Midtown Manhattan, New York City: Springer; p. 183–195. [CrossRef]
• [2] Grafstrom, A. (2010). On Unequal Probability Sampling Designs (Doctorial dissertation). Umea: Umea University; 2010. [CrossRef]
• [3] Horvitz DG, Thompson DJ. A generalization of sampling without replacement from a finite universe. J Am Stat Assoc 1952;47:663–685. [CrossRef]
• [4] Hansen MN, Hurwitz WN. On the theory of sampling from finite Populations. Annal Math Stat 1943;14:333–362. [CrossRef]
• [5] Yates F, Grundy PM. Selection without replacement from within strata with probability proportional to size. J Royal Stat Soc Ser B Method 1953;15:253–261. [CrossRef]
• [6] Fellegi IP. Sampling without replacement with probabilities proportional to size. J Am Stat Assoc 1963;58:183–201. [CrossRef]
• [7] Rao JN. Sampling procedures involving unequal probability selection (Doctorial dissertation). Iowa: Iowa State University; 1961.
• [8] Brewer KR. A Simple Procedure for Sampling pipswor. Australian J Stat 1975;17:166–172. [CrossRef]
• [9] Hanif M, Brewer KR. Sampling with unequal probabilities without replacement: A review. Int Stat Rev 1980;48:317. [CrossRef] [10] Brewer KR, Hanif M. Sampling With Unequal Probabilities. Midtown Manhattan, New York City: Springer; 1983. [CrossRef]
• [11] Li KH. A computer implementation of the yates-grundy draw by draw procedure. J Stat Comput Simul 1994;50:147–151. [CrossRef]
• [12] Gelman A, Meng XL. Applied Bayesian Modeling and Causal Inference from Incomplete‐Data Perspectives: An Essential Journey with Donald Rubin's Statistical Family. Hoboken, New Jersey: Wiley; 2004. [CrossRef]
• [13] Tille Y. Sampling Algorithms. Midtown Manhattan, New York City: Springer; 2006.
• [14] Yu Y. On the inclusion probabilities in some unequal probability sampling plans without replacement. Bernoulli 2012;18:279–289. [CrossRef]
• [15] Tille Y. Sampling and Estimation from Finite Populations. Hoboken, New Jersey: Wiley; 2020. [CrossRef]
• [16] Stamatelatos G, Efraimidis PS. About Weighted Random Sampling in Preferential Attachment Models, 2021. Preprint http://arxiv.org/abs/2102.08173
• [17] Dumelle M, Higham JM, Ver Hoef JM, Olsen AR, Madsen L. A comparison of design-based and model-based approaches for finite population spatial sampling and inference. Methods Ecol Evol 2022;13:2018–2029. [CrossRef]
• [18] Chauvet G. A cautionary note on the Hanurav-Vijayan sampling algorithm. J Survey Stat Method 2022;10:1276–1291. [CrossRef]
• [19] Aubry P. On the correct implementation of the Hanurav-Vijayan selection procedure for unequal probability sampling without replacement. Commun Stat Simul Comput 2023;52:1849–1877. [CrossRef]
• [20] Tille Y. Remarks on some misconceptions about unequal probability sampling without replacement. Comput Sci Rev 2023;47:100533. [CrossRef]
• [21] Efraimidis PS, Spirakis PG. Weighted random sampling with a reservoir. Inform Process Lett 2006;97:181–185. [CrossRef]
• [22] Fellegi IP. Sampling with varying probabilities without replacement: Rotating and non-rotating samples. J Am Stat Assoc 1963;58:183–201. [CrossRef]
• [23] Anadolu Ajansı. Hac kurasına ilişkin merak edilenler, 2021. Available at: https://www.aa.com.tr/tr/turkiye/hac-kurasina-iliskin-merak-edilenler/1694685 Last Accessed Date: 30.07.2024.
• [24] Fog A. Calculation methods for Wallenius' noncentral hypergeometric distribution. Commun Stat Simul Comput 2008;37:258–273. [CrossRef]