# expect value of trying times

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?

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

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