3
$\begingroup$

Each box of a certain breakfast cereal contains one of ten different coupons, each with the same probability. We win a prize if we manage to obtain a complete collection of all the different coupons. How long on average do we have to wait? (For example, suppose we draw the following coupons in order: 5, 2, 3, 7, 5, 1, 1, 4, 8, 4, 1, 9, 10, 2, 3, 3, 6. With the last coupon 6, we have completed our collection, and so we stop after 17 steps.)

$\endgroup$
4
$\begingroup$

Wikipedia has a writeup of the coupon collector's problem. If there are $n$ coupons and you already have $k$ of them, the expected time to get the next is $\frac n{n-k}$ This leads to the time to get them all being $n$ times $H_n$, the $n^{\text{th}}$ Harmonic number. $H_n=\sum_{i=1}^n \frac 1i \approx \log(n)+\gamma$, where $\gamma \approx 0.577$ and you need $n$ times this, so $n \log(n)+n\gamma$

$\endgroup$
  • $\begingroup$ Shouldn't the mean time be $n(\log(n)+\gamma)$? $\endgroup$ – robjohn Jun 11 '15 at 21:18
  • $\begingroup$ @robjohn: Yes, I fixed it. Thanks $\endgroup$ – Ross Millikan Jun 11 '15 at 21:20
0
$\begingroup$

This is a pretty well known problem. I think I'll just direct you here which has the calculation of the expected waiting time to collect all coupons. Let me know if I can explain any of it to you that is not clear.

$\endgroup$
  • $\begingroup$ No it is clear,i will look for that $\endgroup$ – andwilile Oct 15 '13 at 20:50

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