Coupon Coverage

There are $N$ distinct coupon types, and each cereal box holds one type, equally likely and independent of the others. After opening $n$ boxes, how many distinct types does the collector expect to hold?

Reveal solutionHide solution

#An indicator for each type

Let $Y$ count the distinct types among the $n$ boxes, and let $I_i = 1$ when type $i$ shows up at least once. A single box misses type $i$ with probability $\tfrac{N-1}{N}$ , and the boxes are independent, so all $n$ miss it with probability $\left(\tfrac{N-1}{N}\right)^{n}$ and

\E[I_i] = 1 - \left(\frac{N-1}{N}\right)^{n}. \tag{1}

#Sum the indicators

Every type carries the same expected indicator, so summing over the $N$ of them,

\E[Y] = \sum_{i=1}^{N} \E[I_i] = N\left(1 - \left(\frac{N-1}{N}\right)^{n}\right). \tag{2}

Each type is absent from a box with probability (N-1)/N, so after n boxes it is missing with probability ((N-1)/N)^n. Summing the presence indicators gives the expected count, which climbs fast at first and then crawls toward the full set.

Coverage races up while types are still plentiful and then crawls, the same scarcity of the final few types that makes a complete set so slow to finish.