Coupon Collector’s Problem

Context: FIT1058_MOC · expected trials to see all $n$ equally likely outcomes · a sum of geometric waits · answer $n{H}_n$ via linearity

Quick Revision

• 🎯 Objective: trials until all $n$ outcomes seen ➔ $E(Z)=n{H}_n$.
• 📦 Core Components: stagewise geometric waits ➔ summed by linearity.
• ⚡ Key Constraint: $H_n\approx \ln n$ so $E(Z)\approx n\ln n$; the last coupons dominate.

📝 Core

1. The Problem

• Setup ➔ each trial yields one of $n$ equally likely outcomes ($\frac{1}{n}$, with replacement).
• $Z$ ➔ trials until every outcome has appeared.
• Answer ➔ $E(Z)=n{H}_n$, $H_n=1+\frac{1}{2}+\cdots +\frac{1}{n}$.

2. Decompose into Stages

• Stage $k$ ➔ after $k-1$ distinct, new with probability $1-\frac{k-1}{n}$.
• Geometric wait ➔ $X_k\sim \mathrm{Geom}(1-\frac{k-1}{n})$, $E(X_k)=\frac{n}{n-k+1}$.

3. Sum by Linearity

• $Z=\sum X_k$ ➔ $E(Z)={\sum }_k\frac{n}{n-k+1}=n{\sum }_j\frac{1}{j}=n{H}_n$.
• Growth ➔ $H_n\approx \ln n$ ⟹ $E(Z)\approx n\ln n$.

Key identities:

$X_k\sim \mathrm{Geom}\left(1-\frac{k-1}{n}\right),E(X_k)=\frac{n}{n-k+1}$ $E(Z)={\sum }_{k=1}^n\frac{n}{n-k+1}=n{\sum }_{j=1}^n\frac{1}{j}=n{H}_n$

When It Flips: another showcase of linearity — a hard distribution's mean via a chain of independent geometric stages. Applications: black-box output coverage, RNG testing, ecology species counts.

📊 Exam Execution Trace

Manual Execution Trace

$n=4$ coupons:

Step / State	Stage $k$	success prob	$E(X_k)$
0 (Init)	1	1	1
1	2	$\frac{3}{4}$	$\frac{4}{3}$
2	3	$\frac{2}{4}$	2
3	4	$\frac{1}{4}$	4

⚠️ Common Mistakes

• 💡 The last coupon dominates ➔ $X_n$ has success probability $\frac{1}{n}$, so $E(X_n)=n$ alone — most of the wait chases the final few.

🧠 Active Recall

Derive $E(Z)=n{H}_n$ for the coupon collector's problem.

• Hint: Stagewise geometric.

Answer

• Short answer: $X_k\sim \mathrm{Geom}(1-\frac{k-1}{n})$, $E(X_k)=\frac{n}{n-k+1}$; summing gives $n{H}_n$.
• Why: Linearity ➔ $E(\sum X_k)=n\sum 1/j$.

Roughly how many trials, and which stage dominates?

• Hint: $n\ln n$; last coupon.

Answer

• Short answer: $E(Z)\approx n\ln n$ (since $H_n\approx \ln n$); the last coupon averages $E(X_n)=n$.
• Why: Rare last ➔ success probability $\frac{1}{n}$ per trial for the final unseen outcome.