The Coupon Collector Problem

What this lecture covers

This recitation problem solves the classic coupon collector's problem: given a random draw each round from K equally likely categories (here, six possible grades), how many draws are expected before every category has appeared at least once? It builds on linearity of expectation and the geometric distribution from earlier in the course.

You'll see the standard trick of splitting a hard-to-analyze stopping time into a sum of simpler geometric random variables, then using linearity of expectation to add up their individual expectations without worrying about dependence between them.

Key ideas

• Stopping time decomposition: define Y_i as the number of draws until the i-th new category appears, and X_i = Y_(i+1) - Y_i as the number of draws between consecutive new categories.
• Telescoping sum: Y_K (the total time to see all K categories) equals the sum of the X_i differences, so E[Y_K] = E[sum of X_i].
• Geometric distribution per stage: once i categories have been seen, each further draw succeeds (reveals a new category) with probability (K-i)/K, so X_i is geometric with that success parameter.
• Expectation of a geometric variable: for success probability p, the expected number of trials to succeed is 1/p.
• Linearity of expectation: E[sum of X_i] = sum of E[X_i], which holds even though the X_i are not independent of each other in a simple way.
• Harmonic sum result: for K=6, the expected number of draws works out to 6 times a sum of reciprocals, giving approximately 14.7.
• General scaling law: for general K, E[Y_K] = K * sum(1/i for i=1..K-1), which grows roughly like K * ln(K).

Before you watch

• Know the geometric distribution and its expectation formula.
• Be comfortable with linearity of expectation, including that it applies to dependent random variables.
• This problem assumes you've seen discrete random variables and expectation from earlier lectures in the course.

Check your understanding

1. Why is X_i geometric with parameter (K-i)/K rather than a fixed parameter for every i?
2. Why does linearity of expectation apply here even though the X_i are not independent?
3. How does the expected time change if K doubles, based on the K * ln(K) scaling law?
4. What would change in this analysis if the categories were not equally likely?