<pre>
Q: There is a free gift in my breakfast cereal. The manufacturers say that
the gift comes in four different colors, and encourage one to collect
all four (& so eat lots of their cereal). Assuming there is an equal
chance of getting any one of the colors,  what is the expected number
of boxes I must consume to get all four?  Can you generalise to n
colors and/or unequal probabilities?


A: The problem is well known under the name of "COUPON COLLECTOR PROBLEM".
The answer for n equally likely coupons is

(1)		C(n)<code>n*H(n)    with H(n)</code>1+1/2+1/3+...+1/n.

In the unequal probabilities case, with p_i the probability of coupon i,
it becomes

(2)		C(n)<code>int''0^infty (1-prod''{i</code>1}^n (1-exp(-p_i*t))) dt

which reduces to (1) when p_i=1/n (An easy exercise).
In the equal probabilities case  C(n)~n log(n). For a Zipf law,
from (2), we have C(n)~n log^2(n).

A related problem is the [[ Same Day|Birthday Paradox |]]
</pre>
