Coupon Collector Problem

Problem Statement

A cereal company puts one of \(n\) different collectible cards in each box. How many boxes do you expect to buy before collecting all \(n\) cards?

Solution

Let's think about this step by step: when you open the first box, you're guaranteed to get your first unique card. The probability of getting the second unique card in the following attempt is \({n-1 \over n}\) since \(n-1\) cards are still "new" to you. This is a Bernoulli trial that you repeat until success.
The expected number of trials until the first success follows a geometric distribution and the expected number until the success is:

$${1 \over {probability~of~success}} = {n \over n-1}$$ For the third unique card, only \((n-2)\) cards are new, so the probability is \({n-2 \over n}\) and the expected trials is \({n \over n-2}\). This pattern continues: for the \(k\)th unique card, you need \({n \over n-k+1}\) boxes on average.
To collect all \(n\) cards, we need to sum these expectations:
$$\pmb{E[X] = 1 + {n \over n-1} + {n \over n-2} + \ldots + {n \over 1}}$$ For example, with 6 different cards, you'd expect to buy about 14.7 boxes on average. Not convinced? Try the simulation below!

Simulation

show / hide simulation code

import random

def coupon_collector_simulation(num_cards, num_experiments):
    results = []
    
    for _ in range(num_experiments):
        collected_cards = set()
        boxes_bought = 0
        
        while len(collected_cards) < num_cards:
            # Buy a box and get a random card
            card = random.randint(1, num_cards)
            collected_cards.add(card)
            boxes_bought += 1
            
        results.append(boxes_bought)
    
    return results

# Calculate theoretical expected value
def theoretical_expected_boxes(num_cards):
    harmonic_sum = sum(1/i for i in range(1, num_cards + 1))
    return num_cards * harmonic_sum
        

Enter the number of experiments
Enter the number of different cards (n)
	Submit

PREVIOUS

NEXT