Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
7  
This is the coupon collecting problem. –  David Mitra May 29 '12 at 15:22
    
@DavidMitra: Ah okay, thanks - make it an answer and I'll give you green. –  NikolajK May 29 '12 at 15:27
1  
@NickKidman Now that sounds foggy... –  Pedro Tamaroff May 29 '12 at 15:34
add comment

1 Answer

up vote 7 down vote accepted

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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