I'm trying to find the probability mass function for X in the coupon collector's problem which says:
"There are $m \in \mathbb{N} $ different types of coupons, and each coupon
obtained is equally likely to be any one of the $m$ types. Let X be the number of coupons that
need to be collected until the collection contains each of the coupon types. Find the probability mass function of X."
Most if not all of the solutions I've found online seem to use "Stirling numbers of the second kind", which I don't think we're allowed to use without either derivation of the Stirling numbers themselves. Hence, I'm thinking of an approach for finding a closed form for $P(X > k)$, and then determing $P (X = k) = P(X > k) – P(X > k+1)$.
I've found an expression for the above for the case where $m$ is small, say $m=3$, and I obtained that
$$P(X > k) = 3 \cdot \left(\frac{2}{3}\right)^k – 3 \cdot \left(\frac{1}{3}\right)^k$$
But I'm having trouble generalizing this to any m?
So is there some solution to this problem hopefully without using Stirling numbers, whether with the above approach or otherwise? Thank you!
Best Answer
If you want to avoid the Stirling numbers, you will instead need the principle of inclusion exclusion, and a summation.
You had the right idea with looking at $P(X>k)$. The event $\{X>k\}$ is equivalent to saying that at least one coupon is missing after $k$ draws. To find this, first, add up the probabilities of each particular coupon being missing. The result is $$ m\cdot \bigg(\frac{m-1}{m}\bigg)^k $$ However, this double counts all the situations where two coupons are missing. THere are $\binom{m}{2}$ pairs of coupons, so we correct for this with $$ m\cdot \bigg(\frac{m-1}{m}\bigg)^k-\binom{m}2\bigg(\frac{m-2}{m}\bigg)^k $$ However, now the situations with three missing coupons need to be added back in, and so on. The result works out to be $$ P(X>k)=\sum_{i=1}^m(-1)^{i+1}\binom{m}i\bigg(\frac{m-i}{m}\bigg)^k $$