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.

There are X kinds of sticker. Once the player buys a bag he can get Y different stickers. (expectantly) How many bags does he have to buy so that he can collect all kinds of sticker? How about the standard deviation?

share|improve this question
1  
What did you try? –  Did Jul 23 '12 at 12:16
3  
Please see the classic coupon collector problem wiki page, corresponding to $Y=1$. –  Sasha Jul 23 '12 at 13:26

1 Answer 1

Here is a back-of-an-envelope estimate. If $k$ stickers are still missing after some bags were bought, the next bag brings $y\cdot k/x$ new different stickers, in the mean. Thus the mean number $m_n$ of missing stickers after $n$ bags are bought is such that $m_{n+1}\approx m_n-(y/x)\cdot m_n$, that is, $m_n\approx(1-y/x)^n\cdot m_0=(1-y/x)^n\cdot x$. The mean number of missing stickers is $O(1)$ when $(1-y/x)^n\cdot x\approx1$, hence the mean number of bags to buy to complete the collection of stickers is roughly $$ \frac{\log(x)}{\log(x-y)-\log(x)}. $$ Note that, when $y=1$, one recovers in the limit $x\to\infty$ the well-known asymptotics $x\log(x)$.

share|improve this answer

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.