0
$\begingroup$

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?

$\endgroup$

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.