Fri 4 January 2019

Coupon collecting with equal probability

Written by Hongjinn Park in Articles

I love this question because it reminds me of when I grinded for purple loots in World of Warcraft.

Independent trials of picking one of N coupons with equal probability, what is the expected number you have to collect to get a full set? Reasonable question.

Let $X$ bet the number of coupons to collect a full set. So for example the $P(X < N)=0$ since you're not going to collect all N types before N picks.

Now cleverly realize that $X = X_0 + ...$ where each $X_i$ is a RV that equals the number of coupons to collect to get a new type not already collected. From this you notice that each $X_i$ is a Geometric RV with probability $p=\frac{N-i}{N}$ and expected value $\frac{1}{p} = \frac{N}{N-i}$. Important to note is that you start at $X_0$ because you will get a new coupon for sure on the first pick that you don't already have.

Now using the LOE you can do $E[X] = E[X_0+...+X_{N-1}] = E[X_0] +...+ E[X_{N-1}] = \frac{N}{N}+\frac{N}{N-1}+\frac{N}{N-2}+...+\frac{N}{1}$

This grows faster than linear (which makes sense as you add more coupons to collect) but not as fast as $x^2$. It grows at approximately $1.1xlnx$ if my calculations are correct. For example if there are 500 coupons then the expected number of picks is about $3400$ to get a complete set.



Articles

Personal notes I've written over the years.