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)=n*H(n) with H(n)=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)=int_0^infty (1-prod_{i=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 Birthday Paradox

lib/DbaDatabase.php:134: Warning: dba_replace() [<a href='function.dba-replace'>function.dba-replace</a>]: You cannot perform a modification to a database without proper access