 # 399 probability/coupon.p

## Description

This article is from the Puzzles FAQ, by Chris Cole chris@questrel.questrel.com and Matthew Daly mwdaly@pobox.com with numerous contributions by others.

# 399 probability/coupon.p

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?

probability/coupon.s

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" familiar to people
interested in hashing algorithms: With a party of 23 persons,
you are likely (i.e. with probability >50%) to find two with
the same birthday. The non equiprobable case was solved by:
M. Klamkin and D. Newman, Extensions of the birthday
surprise, J. Comb. Th. 3 (1967), 279-282.

Continue to: