Coupon Collection

There are $N$ distinct coupon types, and each cereal box holds one type, equally likely and independent of the others. How many boxes on average are needed to collect at least one of every type?

Reveal solutionHide solution

#Stage the hunt by how many types are held

Break the collection into stages indexed by how many distinct types are already in hand. Let $X_i$ be the extra boxes needed to win the $i$ -th new type once $i-1$ are held. A fresh box shows a new type with probability $p_i = \tfrac{N-i+1}{N}$ , so $X_i$ is geometric with mean $\E[X_i] = \tfrac{N}{N-i+1}$ .

#Sum the stages

Adding the stage costs and reindexing the sum,

\E[X] = \sum_{i=1}^{N} \frac{N}{N-i+1} = N\left(1 + \frac{1}{2} + \cdots + \frac{1}{N}\right) = N H_N. \tag{1}

Winning the i-th new type takes a geometric number of boxes with success rate (N-i+1)/N, so the expected cost N/(N-i+1) climbs as the set fills. The last coupon alone averages N boxes, and the stages sum to N times the harmonic number.

The tail dominates the bill. The very last type, with only a $\tfrac{1}{N}$ chance per box, alone costs an expected $N$ boxes, so completing the set is far slower than filling most of it.