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 [tex]\frac{m - i + 1}{m}[/tex] P r{Xi = n} =[tex](\frac{i-1}{m}) ^{n-1}[/tex] [tex]\frac{m - i + 1}{m}[/tex]
Such a random variable has expectation:
E [Xi ] =[tex]\frac{1}{\frac{m- i + 1}{m} }[/tex] = [tex]\frac{m}{m-i + 1}[/tex]
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 = ∑ [tex]\frac{m}{m-i + 1}[/tex] = m ∑ [tex]\frac{1}{i}[/tex] = 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
