3
$\begingroup$

We are collecing stickers in chocolate bars and whenever we open a bar we get a random new sticker. There are many different stickers and we try to collect them all.

We open the first bar and get a sticker. We open the second bar and we get another sticker, but there is now a chance that it's the one we already got. Doubles are thrown away. As we collect more and more different stickers, the chance gets worse and worse.

So if there are a total of $N$ different possible stickers and we already got $n$, how much chocolate bars $d(N,n)$ do we have to open before we get another one, i.e. the $(n+1)^{th}$ sticker? From this it should also be possible to compute the total number of bars we have to open (sum of average openings).

  • 0
    Related: http://math.stackexchange.com/questions/28905/expected-time-to-roll-all-1-through-6-on-a-die2016-10-17

1 Answers 1

8

This is one of the basic problems in probability known to many as the Coupon collecting problem. The Wiki link has a complete solution.

Incidentally, you should be asking about the expected number of bars to open to obtain the next, not already collected, sticker, not "how much chocolate bars $d(N,n)$ do we have to open ...".