Question

Suppose that each coupon obtained is, independently of what has been previously obtained, equally likely to be any of m different types. Find the expected number of coupons one needs to obtain in order to have at least one of each type?

Answer 1

ANSWER:

E[X] ≈ m ln m

STEP-BY-STEP EXPLANATION:

Hint: Let X be the number needed. It is useful to represent X by

       m      

X =  ∑  Xi

      i=1

where each Xi  is a geometric random variable

Solution: Assume that there is a sufficiently large number of coupons such that removing a finite number of them does not change the probability that a coupon of a given type is draw. Let X be the number of coupons picked

       m      

X =  ∑  Xi

      i=1

where Xi is the number of coupons picked between drawing the (i − 1)th coupon type and drawing i th coupon type. It should be clear that X1 = 1. Also, for each i:

Xi ∼ geometric $\frac{m - i + 1}{m}$ P r{Xi = n} =$(\frac{i-1}{m}) ^{n-1}$ $\frac{m - i + 1}{m}$

Such a random variable has expectation:

E [Xi ] =$\frac{1}{\frac{m- i + 1}{m} }$ = $\frac{m}{m-i + 1}$

Next we use the fact that the expectation of a sum is the sum of the expectation, thus:

                m           m             m                    m

E[X] = E    ∑  Xi  =   ∑ E   Xi  = ∑  $\frac{m}{m-i + 1}$  = m ∑ $\frac{1}{i}$ = mHm

               i=1           i=1             i=1                   i=1

In the case of large m this takes on the limit:

E[X] ≈ m ln m