On inclusion probabilities for weighted random sampling without replacement

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.