3
$\begingroup$

Suppose I have a set of 100 integers. I randomly choose 10 of those, make a note of which ones I selected, and repeat the process. What is the expected number of times this process must be repeated before I see all 100 integers?

I'm also greatly interested in how this is calculated as I'm trying to increase the expected number of times this process is repeated by changing the set sizes.

$\endgroup$
  • 4
    $\begingroup$ You're asking about the coupon collector's problem where the coupons are collected in groups. This is a well-studied problem. See, for instance, section 4 of mat.uab.cat/matmat/PDFv2014/v2014n02.pdf . $\endgroup$ – Rus May Jul 27 '15 at 12:14
  • $\begingroup$ Thank you Rus. This was exactly what I was looking for. $\endgroup$ – jcowfer Jul 27 '15 at 13:10
4
$\begingroup$

As pointed out in a comment, this is the coupon collector's problem with coupons collected in groups (with distinct coupons per group). Let $n$ be the number of coupons and $m$ the number of coupons drawn per group. Denote the number of steps required to draw all coupons by $T$. By inclusion-exclusion,

$$ P(T\le t)=\sum_{j=0}^n(-1)^j\binom nj\left(\frac{\binom{n-j}m}{\binom nm}\right)^t\;. $$

Thus the expected number of steps required is

\begin{align} E[T]&=\sum_{t=0}^\infty P(T\gt t) \\ &= \sum_{t=0}^\infty\sum_{j=1}^n(-1)^{j-1}\binom nj\left(\frac{\binom{n-j}m}{\binom nm}\right)^t \\ &= \sum_{j=1}^n(-1)^{j-1}\binom nj\sum_{t=0}^\infty\left(\frac{\binom{n-j}m}{\binom nm}\right)^t \\ &= \sum_{j=1}^n(-1)^{j-1}\binom nj\frac1{1-\frac{\binom{n-j}m}{\binom nm}}\;. \end{align}

In your case $n=100$ and $m=10$, so

\begin{align} \sum_{j=1}^{100}(-1)^{j-1}\binom{100}j\frac1{1-\frac{\binom{100-j}{10}}{\binom{100}{10}}} \approx49.945 \end{align}

groups have to be drawn on average, corresponding to about $499.45$ coupons, compared to the $100H_{100}\approx518.74$ coupons required on average without groups.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.