Coupon Collecting

Python Puzzles

Back to the Python! homepage

This problem is called the coupon collector’s problem.

A cereal is running a promotion where if you collect all 10 coupons, you win a prize. A coupon is only available if you buy a box of their cereal. What is the average number of box purchases needed in order to collect all 10 coupons?

When I run the following simulation, I get the following:

Minimum number of box purchases needed: 10
Maximum number of box purchases needed: 134
Average number of box purchases needed: 29.21431

The Python code below also includes a histogram to show the distribution of box purchases needed to collect all 10 coupons.

import random
import matplotlib.pyplot as plt

def collect_coupons():
    coupons = set()
    num_purchases = 0
    while len(coupons) < 10:
        coupon = random.randint(1, 10)
        coupons.add(coupon)
        num_purchases += 1
    return num_purchases

num_simulations = 100000
total_purchases = 0
purchases_list = []
for i in range(num_simulations):
    purchases = collect_coupons()
    total_purchases += purchases
    purchases_list.append(purchases)

avg_purchases = total_purchases / num_simulations
print("Average number of box purchases needed:", avg_purchases)

plt.hist(purchases_list, bins=range(1, max(purchases_list)+1), align='left')
plt.xticks(range(1, max(purchases_list)+1, 20))  # show every 20th number
plt.xlabel('Number of box purchases')
plt.ylabel('Frequency')
plt.title('Distribution of box purchases needed to collect all 10 coupons')
plt.show()

min_purchases = min(purchases_list)
max_purchases = max(purchases_list)
avg_purchases = total_purchases / num_simulations
print("Minimum number of box purchases needed:", min_purchases)
print("Maximum number of box purchases needed:", max_purchases)
print("Average number of box purchases needed:", avg_purchases)