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 P r{Xi = n} =
Such a random variable has expectation:
E [Xi
] = =
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 = ∑ = m ∑
= 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