Consider again the coupon collector's problem:

There are $c$ different types of coupon, and each coupon obtained is equally likely to be any one of the $c$ types. Find the probability that the first $n$ coupons which you collect do not form a complete set, and deduce an expression for the mean number of coupons you will need to collect before you have a complete set.

For the probability that the first $n$ coupons do not form a complete set, it will be the complementary probability that the first $n$ coupons do form a complete set, thus: $$ \mathbb{P}(n\text{ coupons, not complete set}) = 1 - {n \choose c} \left(\frac{1}{c}\right)^c. $$ The idea for this expression is that the sequences of length $n$ that have at least the $c$ coupons are equal to the number of ways that $c$ elements can be disposed on a sequence of length $n$, thus ${n \choose c}$. The sequence of $c$ distinct coupons has probability $c^{-c}$, and as I do not care about the remaining $n-c$ spots in the sequence, these can be anything.

For the mean number of coupons needed to collect before having a complete set, I would say: $$ \sum_{m=c}^\infty m {m-1 \choose c-1} \left(\frac{1}{c}\right)^{c-1}\left(\frac{c-1}{c}\right)^{m-c-1}\frac{1}{c}, $$ as in this case for every length $m$ we need to count the number of sequences which contain all the $c$ distinct coupons, but the last coupon of the collection must be in the $m$-th place, so we need to dispose $c-1$ coupons in $m-1$ places. In the remaining $m-c$ places we can allow any coupon except for the last one we need, so the probability is $\frac{c-1}{c}$.

What do you think? If I am correct, is there a way to compute the summation?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.