Skip to main content
To KTH's start page To KTH's start page

Karl Forsbäck: Versatility of the Coupon Collector’s Problem

Time: Thu 2022-04-21 14.00 - 15.00

Location: Kräftriket, Building 6, Room 306

Respondent: Karl Forsbäck

Export to calendar

Abstract: The Coupon Collector’s Problem asks the question of how many coupons, belonging to a set where the probability of all coupons is equal, must be purchased at random before at least one of each type has been acquired.
This thesis explores this specific problem, as well as the generalization to unequal probabilities, using two different methods. The traditional discrete approach, where one coupon is collected at each time unit, makes use of the geometric distribution and the harmonic series. The alternative way is to utilize the Poisson Process. There coupons are collected continuously at an independent probabilistic rate of 1 per time unit, where the times between coupons are exponentially distributed. An example calculating the expected number of draws needed to collect all coupons will be given for each method to illustrate the similarities and differences.

The discrete method is simpler to understand initially, however the continuous approach makes the generalization as well as a mathematical analysis of the problem significantly simpler. This will all be illustrated in a few examples as well. Additionally, it covers two applications of the generalized problem, the Pokemon games and unfair dice. We will see how the games core mechanic, to discover unique creatures, can be explained and quantified using the Poisson Process method. Using the very same method we will show that the way numbers appear on any unfair dice may have a distinctly different distribution from a regular fair dice.