Question

Complete sampling with replacement, sometimes called the coupon collector's problem, is phrased as follows: Suppose you have \(N\) unique items in a bin. At each step, an item is chosen at random, identified, and put back in the bin. The problem asks what is the expected number of steps \(E(N)\) that it takes to draw each unique item at least once. It turns out that \(E(N)=N . H_{N}=N\left(1+\frac{1}{2}+\frac{1}{3}+\cdots+\frac{1}{N}\right) .\) Find \(E(N)\) for \(N=10,20\), and 50 .

Short answer

\(E(10) = 29.29\), \(E(20) = 71.95\), \(E(50) = 224.96\)

Step-by-step solution

Understand the Formula

The formula given is for the expected number of steps needed to collect all unique items at least once when items are drawn with replacement: \(E(N) = N \cdot H_N \). The term \(H_N\) is the \(N\)-th harmonic number, which is defined as \(1 + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{N}\).

Calculate the 10th Harmonic Number

The 10th harmonic number \(H_{10}\) is calculated as follows: \( H_{10} = 1 + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \frac{1}{5} + \frac{1}{6} + \frac{1}{7} + \frac{1}{8} + \frac{1}{9} + \frac{1}{10} = 2.9289682539682538\).

Calculate E(10)

Using the formula \(E(N) = N \cdot H_N\), for \(N = 10\): \[E(10) = 10 \cdot 2.9289682539682538 = 29.289682539682538\].

Calculate the 20th Harmonic Number

The 20th harmonic number \(H_{20}\) is calculated as \(H_{20} = 1 + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{20} = 3.5977396571436823\).

Calculate E(20)

For \(N = 20\): \[E(20) = 20 \cdot 3.5977396571436823 = 71.95479314287365\].

Calculate the 50th Harmonic Number

The 50th harmonic number \(H_{50}\) is \(H_{50} = 1 + \frac{1}{2} + \cdots + \frac{1}{50} = 4.499205338329425\).

Calculate E(50)

For \(N = 50\): \[E(50) = 50 \cdot 4.499205338329425 = 224.96026691647126\].

Key concepts

Coupon Collector's Problem

The Coupon Collector's Problem is a well-known question in probability theory. It explores how many trials are needed to collect all unique instances within a set when sampling is done with replacement. Imagine you have a set of items, like cereal box prizes, and each time you randomly pick one, you might get a new prize or repeat one you already have. The goal is to continue picking until you have all unique prizes.
Each time you draw, there's a chance you might not get something new because the item is put back into the mix after every draw. This creates a situation where patience is required, as some items will be more elusive than others. On average, how long do you need to keep drawing until you have them all? That's what this problem attempts to solve.
The result is not straightforward, as it involves calculating expected values based on probabilities of each draw bringing in a new or repeated item. It provides a fascinating glimpse into how randomness and statistical expectations can predict outcomes.

Harmonic Numbers

Harmonic numbers are central to solving the Coupon Collector's Problem. A harmonic number, represented by \(H_N\), is the sum of the reciprocals of the first \(N\) natural numbers:

• \(H_1 = 1\)
• \(H_2 = 1 + \frac{1}{2}\)
• \(H_3 = 1 + \frac{1}{2} + \frac{1}{3}\)
• And so on until \(N\)

Calculating these harmonic numbers involves adding smaller and smaller increments as \(N\) increases. Although it seems like the increments diminish in effect, they cumulatively hold their significance.
There is a relationship between harmonic numbers and the natural logarithm, as these numbers approximately grow as \(\ln(N) + \gamma\), where \(\gamma\) is the Euler-Mascheroni constant.
In the context of the Coupon Collector's Problem, harmonic numbers tell us how the expected time to collect all items grows as the number of unique items increases. Essentially, these numbers help to gauge how tough it may become to complete the collection as the variety increases.

Expected Value

In probability theory, the concept of the expected value helps predict the average outcome of a random process over time. It's akin to finding a central tendency measure, like the mean or average drawn from a large number of trials.
When considering the Coupon Collector's Problem, the expected value \(E(N)\) is calculated using the formula \(E(N) = N \cdot H_N\). This means that the expected number of draws needed to collect all \(N\) unique items is the product of \(N\), the total number of items, and the \(N\)-th harmonic number \(H_N\).
This formula is derived from testing how often you'd typically encounter a new item upon drawing. Since some duplicates will naturally occur, the formula effectively accounts for repeated items by tying together combinatorial probabilities and expected values. Understanding this helps anticipate how many attempts, on average, are needed to gather each unique element in scenarios like drawing cards or collecting coupons.