# 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: