The Coupon Collector Problem and the Expected Number of Draws

Collecting all n coupon types takes n times the nth harmonic number draws on average, about 225 draws to finish a 50 item set.

Collecting a full set of n distinct coupons, drawing one at random with replacement each time, takes n times the nth harmonic number draws on average. For a set of 50 distinct items the harmonic number, the sum of one over k for every whole number k from one up to n, is about 4.499, so the expected number of draws is fifty times 4.499, or about 225.

There are n distinct coupon types, and each draw independently returns one of the n types with equal probability one over n, with replacement, so the same type can be drawn many times before the set is complete. The question asks for the expected number of draws needed until every one of the n types has appeared at least once.

This is the same structure behind collecting every unique card in a random pack, seeing every face of a die, or a desk receiving order flow tagged with one of n counterparties and wanting to know how long until every counterparty has traded at least once.

Break the collecting process into stages by how many distinct types have been seen so far. Stage k begins the moment the k-th distinct new type appears and ends when the (k plus 1)-th new type appears. During stage k, exactly k of the n types have already been seen, so each draw has probability (n minus k) over n of landing on a type not yet seen.

The number of draws needed to end stage k follows a geometric distribution with success probability (n minus k) over n. The expected number of draws for a geometric distribution with success probability p is one over p, so the expected length of stage k is n over (n minus k).