# The coupon collectors problem [closed]

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.)

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$
• Shouldn't the mean time be $n(\log(n)+\gamma)$? – robjohn Jun 11 '15 at 21:18