Introduction to the Coupon Collector's Problem

Introduction

Imagine a cereal company puts one of n different prizes in every box, chosen uniformly at random. You buy box after box. How many boxes do you need to complete the collection?

This is the Coupon Collector's Problem, a classic from probability theory. It is not a hard problem to state, and the answer is known exactly: the expected number of draws is $n \cdot H(n)$ , where $H(n) = 1 + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{n}$ is the harmonic number — which grows like $n \cdot \ln(n)$ for large $n$ .

The formula is beautiful, but the feeling behind it is what stays with you. The first few coupons arrive almost immediately. The last few feel like they take forever — because they do. When you already have $n-1$ distinct coupons, the chance that the next draw gives you the missing one is only $\frac{1}{n}$ . On average you need $n$ more draws just for that final piece.

That asymmetry — fast start, agonizing finish — is not just a quirk of collecting. It appears in hashing, networking, testing, and anywhere randomness is used to cover a set of possibilities.

Try It

Choose the set size n and press Collect all to run one simulation. The bar chart shows how many draws were needed for each new distinct coupon. Watch how the bars grow taller as the set fills up — each new coupon becomes rarer.

<div class="controls">
  <label>Set size <b id="nLabel">8</b>
    <input type="range" id="nSlider" min="4" max="20" value="8" />
  </label>
  <button id="runBtn" type="button">Collect all</button>
  <button id="resetBtn" type="button" class="ghost">Reset</button>
</div>
<div class="summary" id="summary"></div>
<div class="chart-wrap">
  <canvas id="chart"></canvas>
</div>
<div class="formula" id="formula"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; padding: .5rem; }
.controls { display: flex; align-items: center; gap: .8rem; flex-wrap: wrap; margin-bottom: .6rem; }
label { font-size: .9rem; display: flex; align-items: center; gap: .4rem; }
input[type=range] { width: 120px; accent-color: #1d3557; }
button { font: 600 14px system-ui, sans-serif; padding: .4rem .85rem;
         border: 1px solid #1d3557; background: #1d3557; color: #fff;
         border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
.summary { font-size: .95rem; font-weight: 600; min-height: 1.4em; margin-bottom: .4rem; }
.summary.ok { color: #0a7d33; }
.chart-wrap { width: 100%; overflow-x: auto; }
canvas { display: block; }
.formula { font-size: .85rem; color: #444; margin-top: .5rem; line-height: 1.5; }
.formula b { color: #1d3557; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Coupon Collector simulation.
// n = set size. Draw uniformly at random from {0..n-1} until all seen.
// Track draws_needed[k] = draws to get the k-th new distinct coupon.
// Expected draws for k-th new = n / (n - k + 1). Total = n * H(n).

const slider = document.getElementById('nSlider');
const nLabel = document.getElementById('nLabel');
const runBtn = document.getElementById('runBtn');
const resetBtn = document.getElementById('resetBtn');
const summary = document.getElementById('summary');
const formulaDiv = document.getElementById('formula');
const canvas = document.getElementById('chart');
const ctx = canvas.getContext('2d');

function harmonic(n) {
  let h = 0;
  for (let i = 1; i <= n; i++) h += 1 / i;
  return h;
}

function simulate(n) {
  const seen = new Set();
  const drawsPerNew = []; // drawsPerNew[k] = draws to get (k+1)-th new coupon
  let drawCount = 0;
  let drawsSinceLastNew = 0;
  while (seen.size < n) {
    const coupon = Math.floor(Math.random() * n);
    drawCount++;
    drawsSinceLastNew++;
    if (!seen.has(coupon)) {
      seen.add(coupon);
      drawsPerNew.push(drawsSinceLastNew);
      drawsSinceLastNew = 0;
    }
  }
  return { total: drawCount, drawsPerNew };
}

function drawChart(n, drawsPerNew) {
  const BAR_W = 28;
  const GAP = 4;
  const PAD_L = 36;
  const PAD_B = 28;
  const PAD_T = 14;
  const width = PAD_L + n * (BAR_W + GAP) + GAP + 20;
  const maxVal = Math.max(...drawsPerNew, 1);
  const chartH = 160;
  canvas.width = width;
  canvas.height = chartH + PAD_B + PAD_T;
  ctx.clearRect(0, 0, canvas.width, canvas.height);

  // axes
  ctx.strokeStyle = '#ccc';
  ctx.lineWidth = 1;
  ctx.beginPath();
  ctx.moveTo(PAD_L, PAD_T);
  ctx.lineTo(PAD_L, PAD_T + chartH);
  ctx.lineTo(PAD_L + n * (BAR_W + GAP), PAD_T + chartH);
  ctx.stroke();

  // expected line: E[k-th new] = n / (n - k + 1)
  ctx.strokeStyle = '#e63946';
  ctx.lineWidth = 1.5;
  ctx.setLineDash([4, 3]);
  ctx.beginPath();
  for (let k = 1; k <= n; k++) {
    const expected = n / (n - k + 1);
    const x = PAD_L + (k - 1) * (BAR_W + GAP) + BAR_W / 2;
    const y = PAD_T + chartH - (expected / maxVal) * chartH;
    k === 1 ? ctx.moveTo(x, y) : ctx.lineTo(x, y);
  }
  ctx.stroke();
  ctx.setLineDash([]);

  // bars
  for (let k = 0; k < n; k++) {
    const val = drawsPerNew[k];
    const barH = (val / maxVal) * chartH;
    const x = PAD_L + k * (BAR_W + GAP) + GAP / 2;
    const y = PAD_T + chartH - barH;
    // gradient: early coupons blue, late coupons orange
    const t = k / (n - 1);
    const r = Math.round(29 + t * (230 - 29));
    const g = Math.round(53 + t * (100 - 53));
    const b = Math.round(87 + t * (20 - 87));
    ctx.fillStyle = `rgb(${r},${g},${b})`;
    ctx.beginPath();
    ctx.roundRect(x, y, BAR_W, barH, [3, 3, 0, 0]);
    ctx.fill();

    // value label on top of bar if fits
    if (barH > 14) {
      ctx.fillStyle = '#fff';
      ctx.font = 'bold 10px system-ui';
      ctx.textAlign = 'center';
      ctx.fillText(val, x + BAR_W / 2, y + 11);
    }

    // x-axis label
    ctx.fillStyle = '#666';
    ctx.font = '10px system-ui';
    ctx.textAlign = 'center';
    ctx.fillText(k + 1, x + BAR_W / 2, PAD_T + chartH + 14);
  }

  // y-axis ticks
  ctx.fillStyle = '#888';
  ctx.font = '10px system-ui';
  ctx.textAlign = 'right';
  const ticks = [1, Math.round(maxVal / 2), maxVal];
  for (const t of ticks) {
    const y = PAD_T + chartH - (t / maxVal) * chartH;
    ctx.fillText(t, PAD_L - 4, y + 3);
    ctx.strokeStyle = '#eee';
    ctx.lineWidth = 1;
    ctx.beginPath();
    ctx.moveTo(PAD_L, y);
    ctx.lineTo(PAD_L + n * (BAR_W + GAP), y);
    ctx.stroke();
  }

  // legend
  ctx.setLineDash([4, 3]);
  ctx.strokeStyle = '#e63946';
  ctx.lineWidth = 1.5;
  ctx.beginPath();
  ctx.moveTo(PAD_L + 2, PAD_T + chartH - 6);
  ctx.lineTo(PAD_L + 22, PAD_T + chartH - 6);
  ctx.stroke();
  ctx.setLineDash([]);
  ctx.fillStyle = '#e63946';
  ctx.font = '10px system-ui';
  ctx.textAlign = 'left';
  ctx.fillText('Expected', PAD_L + 24, PAD_T + chartH - 3);
}

function run() {
  const n = parseInt(slider.value, 10);
  const { total, drawsPerNew } = simulate(n);
  const expected = n * harmonic(n);
  const ratio = (total / expected).toFixed(2);
  summary.textContent = fmt('Total draws: %total%  (formula predicts %round%, ratio %ratio%)', { total: total, round: Math.round(expected), ratio: ratio });
  summary.className = 'summary ok';
  drawChart(n, drawsPerNew);
  const gamma = 0.5772;
  formulaDiv.innerHTML =
    fmt('<b>Formula:</b> E[draws] = n·H(n) ≈ n·ln(n) + γ·n<br>For n = n=%n%: n·H(n) = <b>%expected%</b>, this run used <b>%total%</b>.<br>Bar chart: draws needed for each new coupon (blue = early, orange = late).', { n: n, expected: expected.toFixed(1), total: total });
  console.log(fmt('result n=%n% total=%total% expected=%expected% ratio=%ratio%', { n: n, total: total, expected: expected.toFixed(2), ratio: ratio }));
}

function reset() {
  summary.textContent = '';
  summary.className = 'summary';
  formulaDiv.innerHTML = '';
  ctx.clearRect(0, 0, canvas.width, canvas.height);
}

slider.addEventListener('input', () => { nLabel.textContent = slider.value; reset(); });
runBtn.addEventListener('click', run);
resetBtn.addEventListener('click', reset);

// draw initial blank chart axes
const initN = parseInt(slider.value, 10);
canvas.width = 36 + initN * 32 + 20;
canvas.height = 202;

<div class="controls">
  <label>Set size <b id="nLabel">8</b>
    <input type="range" id="nSlider" min="4" max="20" value="8" />
  </label>
  <button id="runBtn" type="button">Collect all</button>
  <button id="resetBtn" type="button" class="ghost">Reset</button>
</div>
<div class="summary" id="summary"></div>
<div class="chart-wrap">
  <canvas id="chart"></canvas>
</div>
<div class="formula" id="formula"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; padding: .5rem; }
.controls { display: flex; align-items: center; gap: .8rem; flex-wrap: wrap; margin-bottom: .6rem; }
label { font-size: .9rem; display: flex; align-items: center; gap: .4rem; }
input[type=range] { width: 120px; accent-color: #1d3557; }
button { font: 600 14px system-ui, sans-serif; padding: .4rem .85rem;
         border: 1px solid #1d3557; background: #1d3557; color: #fff;
         border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
.summary { font-size: .95rem; font-weight: 600; min-height: 1.4em; margin-bottom: .4rem; }
.summary.ok { color: #0a7d33; }
.chart-wrap { width: 100%; overflow-x: auto; }
canvas { display: block; }
.formula { font-size: .85rem; color: #444; margin-top: .5rem; line-height: 1.5; }
.formula b { color: #1d3557; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Coupon Collector simulation.
// n = set size. Draw uniformly at random from {0..n-1} until all seen.
// Track draws_needed[k] = draws to get the k-th new distinct coupon.
// Expected draws for k-th new = n / (n - k + 1). Total = n * H(n).

const slider = document.getElementById('nSlider');
const nLabel = document.getElementById('nLabel');
const runBtn = document.getElementById('runBtn');
const resetBtn = document.getElementById('resetBtn');
const summary = document.getElementById('summary');
const formulaDiv = document.getElementById('formula');
const canvas = document.getElementById('chart');
const ctx = canvas.getContext('2d');

function harmonic(n) {
  let h = 0;
  for (let i = 1; i <= n; i++) h += 1 / i;
  return h;
}

function simulate(n) {
  const seen = new Set();
  const drawsPerNew = []; // drawsPerNew[k] = draws to get (k+1)-th new coupon
  let drawCount = 0;
  let drawsSinceLastNew = 0;
  while (seen.size < n) {
    const coupon = Math.floor(Math.random() * n);
    drawCount++;
    drawsSinceLastNew++;
    if (!seen.has(coupon)) {
      seen.add(coupon);
      drawsPerNew.push(drawsSinceLastNew);
      drawsSinceLastNew = 0;
    }
  }
  return { total: drawCount, drawsPerNew };
}

function drawChart(n, drawsPerNew) {
  const BAR_W = 28;
  const GAP = 4;
  const PAD_L = 36;
  const PAD_B = 28;
  const PAD_T = 14;
  const width = PAD_L + n * (BAR_W + GAP) + GAP + 20;
  const maxVal = Math.max(...drawsPerNew, 1);
  const chartH = 160;
  canvas.width = width;
  canvas.height = chartH + PAD_B + PAD_T;
  ctx.clearRect(0, 0, canvas.width, canvas.height);

  // axes
  ctx.strokeStyle = '#ccc';
  ctx.lineWidth = 1;
  ctx.beginPath();
  ctx.moveTo(PAD_L, PAD_T);
  ctx.lineTo(PAD_L, PAD_T + chartH);
  ctx.lineTo(PAD_L + n * (BAR_W + GAP), PAD_T + chartH);
  ctx.stroke();

  // expected line: E[k-th new] = n / (n - k + 1)
  ctx.strokeStyle = '#e63946';
  ctx.lineWidth = 1.5;
  ctx.setLineDash([4, 3]);
  ctx.beginPath();
  for (let k = 1; k <= n; k++) {
    const expected = n / (n - k + 1);
    const x = PAD_L + (k - 1) * (BAR_W + GAP) + BAR_W / 2;
    const y = PAD_T + chartH - (expected / maxVal) * chartH;
    k === 1 ? ctx.moveTo(x, y) : ctx.lineTo(x, y);
  }
  ctx.stroke();
  ctx.setLineDash([]);

  // bars
  for (let k = 0; k < n; k++) {
    const val = drawsPerNew[k];
    const barH = (val / maxVal) * chartH;
    const x = PAD_L + k * (BAR_W + GAP) + GAP / 2;
    const y = PAD_T + chartH - barH;
    // gradient: early coupons blue, late coupons orange
    const t = k / (n - 1);
    const r = Math.round(29 + t * (230 - 29));
    const g = Math.round(53 + t * (100 - 53));
    const b = Math.round(87 + t * (20 - 87));
    ctx.fillStyle = `rgb(${r},${g},${b})`;
    ctx.beginPath();
    ctx.roundRect(x, y, BAR_W, barH, [3, 3, 0, 0]);
    ctx.fill();

    // value label on top of bar if fits
    if (barH > 14) {
      ctx.fillStyle = '#fff';
      ctx.font = 'bold 10px system-ui';
      ctx.textAlign = 'center';
      ctx.fillText(val, x + BAR_W / 2, y + 11);
    }

    // x-axis label
    ctx.fillStyle = '#666';
    ctx.font = '10px system-ui';
    ctx.textAlign = 'center';
    ctx.fillText(k + 1, x + BAR_W / 2, PAD_T + chartH + 14);
  }

  // y-axis ticks
  ctx.fillStyle = '#888';
  ctx.font = '10px system-ui';
  ctx.textAlign = 'right';
  const ticks = [1, Math.round(maxVal / 2), maxVal];
  for (const t of ticks) {
    const y = PAD_T + chartH - (t / maxVal) * chartH;
    ctx.fillText(t, PAD_L - 4, y + 3);
    ctx.strokeStyle = '#eee';
    ctx.lineWidth = 1;
    ctx.beginPath();
    ctx.moveTo(PAD_L, y);
    ctx.lineTo(PAD_L + n * (BAR_W + GAP), y);
    ctx.stroke();
  }

  // legend
  ctx.setLineDash([4, 3]);
  ctx.strokeStyle = '#e63946';
  ctx.lineWidth = 1.5;
  ctx.beginPath();
  ctx.moveTo(PAD_L + 2, PAD_T + chartH - 6);
  ctx.lineTo(PAD_L + 22, PAD_T + chartH - 6);
  ctx.stroke();
  ctx.setLineDash([]);
  ctx.fillStyle = '#e63946';
  ctx.font = '10px system-ui';
  ctx.textAlign = 'left';
  ctx.fillText('Expected', PAD_L + 24, PAD_T + chartH - 3);
}

function run() {
  const n = parseInt(slider.value, 10);
  const { total, drawsPerNew } = simulate(n);
  const expected = n * harmonic(n);
  const ratio = (total / expected).toFixed(2);
  summary.textContent = fmt('Total draws: %total%  (formula predicts %round%, ratio %ratio%)', { total: total, round: Math.round(expected), ratio: ratio });
  summary.className = 'summary ok';
  drawChart(n, drawsPerNew);
  const gamma = 0.5772;
  formulaDiv.innerHTML =
    fmt('<b>Formula:</b> E[draws] = n·H(n) ≈ n·ln(n) + γ·n<br>For n = n=%n%: n·H(n) = <b>%expected%</b>, this run used <b>%total%</b>.<br>Bar chart: draws needed for each new coupon (blue = early, orange = late).', { n: n, expected: expected.toFixed(1), total: total });
  console.log(fmt('result n=%n% total=%total% expected=%expected% ratio=%ratio%', { n: n, total: total, expected: expected.toFixed(2), ratio: ratio }));
}

function reset() {
  summary.textContent = '';
  summary.className = 'summary';
  formulaDiv.innerHTML = '';
  ctx.clearRect(0, 0, canvas.width, canvas.height);
}

slider.addEventListener('input', () => { nLabel.textContent = slider.value; reset(); });
runBtn.addEventListener('click', run);
resetBtn.addEventListener('click', reset);

// draw initial blank chart axes
const initN = parseInt(slider.value, 10);
canvas.width = 36 + initN * 32 + 20;
canvas.height = 202;

Result

Console

Notice the pattern: the first coupon always takes exactly 1 draw. The second takes on average $\frac{n}{n-1}$ . The $k$ -th new coupon takes on average $\frac{n}{n-k+1}$ draws. Add them all up and you get $n \cdot H(n)$ — the harmonic series in disguise. Press Collect all several times to see the randomness, then compare the actual total with the formula's prediction.

The Real Math

The derivation is a masterpiece of elementary probability.

Phase $k$ : once you hold $k-1$ distinct coupons, each draw independently hits the missing coupons with probability $\frac{n-k+1}{n}$ . The number of draws to get the $k$ -th new coupon follows a geometric distribution with success probability $p = \frac{n-k+1}{n}$ , so its expected value is $\frac{n}{n-k+1}$ .
Total expectation: by linearity, the expected total draws is

\sum_{k=1}^{n} \frac{n}{n-k+1} = n \left(1 + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{n}\right) = n \cdot H(n).

Asymptotic: $H(n) \approx \ln(n) + \gamma$ (where $\gamma \approx 0.5772$ is the Euler–Mascheroni constant), so the expected total is approximately $n \cdot \ln(n) + \gamma \cdot n$ .
Concentration: the actual number of draws concentrates tightly around this mean. A Markov / union-bound argument shows that the probability of needing more than $n(\ln n + c)$ draws falls as $e^{-c}$ — so exceeding the mean by even $10n$ extra draws is already very unlikely.
Status: fully solved. The exact formula $n \cdot H(n)$ has been known since at least the 18th century (attributed to de Moivre and later to various probabilists). There is no open question about the expected value — only richer variants (e.g., non-uniform distributions, partial collections) remain active research.

The result shows up in disguise everywhere: a randomized algorithm that samples random inputs until all cases are covered, a hash table filling all buckets, or a test suite hitting all code paths — each is a coupon collector in hiding.

Where It Matters

The coupon collector's bound governs any situation where random trials must hit every member of a finite set:

Hash tables and load balancing: when $n$ items are hashed uniformly into $n$ buckets, how many inserts before every bucket is occupied? The answer is $n \cdot \ln(n)$ — exactly the coupon collector. This drives the analysis of open-addressing hash tables and birthday-paradox collision estimates.
Randomized coverage testing: a test suite that picks random inputs needs about $n \cdot \ln(n)$ tests to hit all $n$ code paths at least once. This is the probabilistic basis for random fuzzing strategies.
Network broadcasting: gossip protocols spread a message to $n$ nodes by randomly forwarding it. The time until every node has heard it is $O(n \cdot \ln(n))$ rounds — a coupon collector argument in each round.
DNA and genome shotgun sequencing: to cover an entire genome of length $n$ with random short reads, you need roughly $\frac{n \cdot \ln(n)}{L}$ reads of length $L$ to ensure no region is missed. The coupon collector bound gave the first rigorous estimates in early sequencing projects.
Sticker albums and card games: every collector experiences the phenomenon directly — the last few cards in a Panini album or trading card set feel impossibly rare, and they are: the expected number of packs for the final sticker is $n$ packs all by itself.

Understanding why the last few take so long is not just trivia. It is the key insight behind why birthday attacks on hash functions are cheaper than expected, why random testing needs more runs than intuition suggests, and why complete coverage is always harder than partial coverage.

Conclusion

The Coupon Collector's Problem is one of the most elegant results in probability: a simple question about collecting prizes yields an exact formula involving the harmonic series, and that formula turns out to govern a surprising range of real phenomena.

The key insight is the asymmetry of rarity. Early draws are cheap — almost any new draw gives you something new. But as the set fills up, each remaining coupon becomes rarer, and the expected wait grows as $\frac{n}{\text{remaining}}$ . Summing those waits produces the logarithmic factor that makes complete coverage so much harder than partial coverage.

Next time you find yourself buying one last pack, waiting for one last random event, or running one last test — remember that you are not unlucky. You have hit the fundamental cost of completeness, and the math says the last few will always feel like forever.

Comments

Loading comments...

https://www.kipuhub.com/en/article/coupon-collector/Content licensed under CC BY-NC 4.0.

Cookies & privacy

The Coupon Collector

How long does it take to collect them all?