Introduction

Imagine that your preferred cereal brand is hosting a contest where each box contains a coupon marked with a number ranging from 1 to N. To win a prize, you must collect all distinct coupons from 1 to N. When purchasing a new box, the probability of receiving a coupon labeled with number i (where i = 1, …, N) is uniformly 1/N.

A logical question arises: how many boxes must you purchase to have a sufficiently high chance of winning? This dilemma is well-explored in probability theory and is commonly referred to as the "Coupon Collector problem." In this article, we will investigate how to approach this question.

What is the Expected Number of Boxes to Purchase?

Given the randomness involved, an essential inquiry is how many boxes one should expect to buy to achieve a win. To find this expectation, we define a random variable Xᵢ for each i = 1, …, N. X₁ represents the number of boxes needed to obtain the first unique coupon. Since we start with no coupons, it follows that X₁ = 1.

Next, we consider X₂, which indicates how many more boxes are required to obtain a second distinct coupon. For X₃, we analyze how many additional boxes are necessary to collect a third distinct coupon, and so on.

To illustrate, consider the scenario where N = 3 and the sequence of coupons in the boxes purchased is as follows: 1, 1, 3, 1, 3, 3, 2. In this case:

• For X₁, we find a new coupon immediately, hence X₁ = 1.
• The second box contains a coupon already in our collection, so we buy a third box, obtaining a new coupon (3). Therefore, X₂ = 2.
• Finally, we buy four additional boxes to discover coupon number 2, resulting in X₃ = 4.

In total, this means we have purchased X₁ + X₂ + X₃ = 7 boxes to collect all distinct coupons.

Now, we aim to compute the expected value of the random variable X, which is the sum of all Xᵢ for i = 1, …, N. Utilizing the useful property known as the Linearity of Expectation, we can derive the expected values for each Xᵢ.

For X₁, we have E[X₁] = 1. For X₂, given that we already possess one coupon, the probability of acquiring a new one is (N-1)/N. This implies that X₂ follows a geometric distribution with a success probability of (N-1)/N. The expected value for X₂ is thus 1/(N-1)/N.

Continuing this analysis, the expected value for the variable Xᵢ is derived from the success probability 1 - (i-1)/N = (N-i+1)/N. Summing all these expected values reveals that the total expected number of boxes purchased can be represented as:

This expression involves the N-th harmonic number, which approximates to ln N. Therefore, we conclude:

E[X] = N * Hₙ, where Hₙ is the N-th harmonic number.

Understanding the Probability of Exceeding the Expected Value

While we can compute the expected number of boxes required, it’s also essential to explore the probability of needing to purchase significantly more boxes than anticipated. A straightforward approach to this is applying Markov's inequality, which states that for any non-negative random variable X, and t > 1:

If we set t = 2, the result indicates that with at least 50% probability, the number of boxes bought will not exceed 4N ln N. Similarly, at least 75% of the time, the number will not surpass 8N ln N.

For further details on Markov's inequality, consult additional resources or prior articles.

To strengthen our analysis, we consider buying T ≥ 1 boxes and calculate the likelihood of not obtaining coupon number i in any of these T purchases. The probability of not finding coupon i in a single box is 1 - 1/N. Thus, the probability of missing it across T boxes is:

(1 - 1/N)ᵀ

Utilizing useful inequalities, we can derive a stronger probability bound. Setting T = 2N ln N, we can conclude:

If T = 2N ln N boxes are purchased, the chance of winning approaches:

The first video, "The Coupon Collector's Problem," provides deeper insights into this fascinating topic.

The second video, "The Coupon Collector Problem," elaborates on the implications and calculations surrounding this problem.

This comprehensive analysis showcases how we can compute not only the expected number of boxes needed to win but also the associated probabilities, providing a well-rounded understanding of the Coupon Collector problem.