Discrete Stochastic Processes

Lesson 5 of 10

The Coupon Collector

How many draws to collect all n types? Each new type is its own geometric wait.

The idea

Split the wait into stages. With i−1i-1 types collected, a new type arrives with probability n−i+1n\frac{n-i+1}{n}, so that stage is geometric with mean nn−i+1\frac{n}{n-i+1}. Add the stages:

E[T]=n(1+12+⋯+1n)=nHn≈nln⁡n+0.58 n.E[T] = n\left(1 + \tfrac12 + \cdots + \tfrac1n\right) = n H_n \approx n \ln n + 0.58\,n.

All six faces of a die: 6H6=14.76 H_6 = 14.7 rolls.