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?
expect value of trying times
0
$\begingroup$
probability
-
3Please see the classic [coupon collector problem](http://en.wikipedia.org/wiki/Coupon_collector%27s_problem) wiki page, corresponding to $Y=1$. – 2012-07-23
1 Answers
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)$.