0
$\begingroup$

Is there an efficient algorithm to calculate the inclusion probabilities (the probability that an item will be included in a sample) in the Yates-Grundy draw-by-draw sampling?

Sampling description: We have $n$ items each with probabilities $p_1, \dots, p_n$ of being selected in the first draw. We then sample without replacement the items one by one with probabilities proportional to the original $p_i$.

I looked in the book Brewer, Muhammad: Sampling with Unequal Probabilities and this is described on p. 24, but the equation (2.2.1) seems to work for sample of size 2 only.

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ How many items are you sampling? $\endgroup$
    – Yuval Peres
    Commented Oct 18, 2019 at 8:33
  • $\begingroup$ @YuvalPeres About 10. I am calculating this now by exhaustive enumeration of all the possibilities, which is even for this small number too computationally expensive. $\endgroup$
    – Josef Ondrej
    Commented Oct 18, 2019 at 15:03

1 Answer 1

Reset to default
0
$\begingroup$

Unfortunately, there seems to exist no efficient algorithm to calculate the inclusion probabilities in the Yates-Grundy draw-by-draw sampling procedure—see the comment on "weighted random sampling without replacement with defined weights" (WRS) in Efraimidis (2015). However, in practice, you can use fast simulation algorithms to obtain point estimates with very tight confidence intervals—see Efraimidis and Spirakis (2006).

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .