Every now and then, someone calls for help to complete a collection from items you can find in packs of food.
How many should you buy ?
Well, if the collection is large, the odds are you should not get started in such an endeavour ;) Let’s see why.
This is well researched. The Coupon collector’s problem is a well-known problem in probability theory that models the scenario where a collector is trying to collect a complete set of items.
The problem is as follows:
Suppose there are n different types of items, and each time the collector makes a purchase, they receive a random item from the set of n items. The collector continues to make purchases until they have collected all n items.
On average, how many purchases must the collector make to collect all n items?
The maths are well understood and some can explain it way better than me. However even though I suck at math I can write Python all day.
The Monte Carlo method is a powerful tool in probability theory for approximating complex problems. In the following piece of code, the Monte Carlo method will approximate the solution to the Coupon collector’s problem.
import random
def buy_meals_until_all_toys(n = 4, iterlimit=5000):
owned_toys = [False] * n
for i in range(iterlimit):
owned_toys[random.randrange(0, n)] = True
if all(owned_toys):
return i+1
raise Exception(f'Expected simulation to finish in {iterlimit} iterations.')
def estimate_expectation(nb_toys=4, nb_iterations=5000):
total = 0
assert(nb_iterations > 0)
for i in range(nb_iterations):
total += buy_meals_until_all_toys(nb_toys)
return total/nb_iterations
print(estimate_expectation(94))
The code consists of two functions. The buy_meals_until_all_toys function simulates the purchase of meals or toys until all the toys have been collected. The function takes in two parameters, n and iterlimit, which represent the number of different types of toys and the maximum number of iterations to run the simulation, respectively. It returns the number of purchases made to complete the collection.
The estimate_expectation function uses the buy_meals_until_all_toys function to estimate the expected number of purchases required to complete a set of n toys. The function takes in two parameters, nb_toys and nb_iterations, which represent the number of different types of toys and the number of iterations to run the simulation, respectively.
In the “Gaulois” example, there are 94 items that you can find, hence the 94 at the end.
Let’s run it:
$ python main.py
480.4298
With 94 items to find, you’ll need to buy on average 480 packs in order to complete the french map of regions. That’s a lot of meals !
But wait.
Ogden’s ‘Guinea Gold’ cigarettes famously had collections of cards with their cigarettes. There was a new collection every year or so. The 1901 collection contained 1148 cards!,
Let’s modify or piece of code.
>>> estimate_expectation(1148, 10_000, 100_000)
8736.6202
It takes a while, both to get the answer and to complete the collection of cards.