Coupon Collector vs. Geometric Distribution: Catching All 150 Pokémon

Question

I've encountered a problem and would like your insights. The problem involves determining the number of tries needed to catch all 150 unique Pokémon.

Problem Statement: How many tries will it take, on average, to catch all 150 unique Pokémon, assuming each Pokémon is equally likely to be caught on any given try?

My Findings: Using the coupon collector's problem approach, the expected number of tries to catch all 150 unique Pokémon is about 838.1776 tries.

Expected number of tries $\approx $ $150(\log(150)+γ)$ / Where $γ$ is the Euler-Mascheroni constant.

I ran a Python simulation 100,000 times and got an average result of 838.69336, which is very close to the theoretical value.

Conflicting Result: However, a mathematics professor in a YouTube video used the geometric distribution and estimated the number of tries to be 752.

My Question: What could be the source of this difference? Why does the coupon collector's problem give a higher expected number of tries compared to the geometric distribution method used by the professor?

My math knowledge is limited to high school level, so any explanations or insights would be helpful. Thank you!

Answer 1

The solution to the coupon collector problem says that the expected number of tries is exactly

$$150 H_{150} = 838.7 \dots$$

where $H_n = 1 + \dots + \frac{1}{n}$ is the $n^{th}$ harmonic number. I am going to guess (I didn't watch the whole video) that Numberphile used a very common asymptotic approximation to the harmonic number, namely

$$H_n \approx \ln n.$$

If you use that approximation you get

$$150 \ln 150 = \color{red}{751.6} \dots $$

which as you can see is actually quite off! Using

$$H_n \approx \ln n + \gamma$$

as you did produces the considerably more accurate

$$150 (\ln 150 + \gamma) = 838.\color{red}{2} \dots $$

and you can get as many digits of accuracy as you want by either asking WolframAlpha to calculate $150 H_{150}$ exactly (the simulation agrees with the exact answer up to $4$ digits but not $5$, so it is actually more accurate than the $\gamma$ approximation) or using more terms in the known asymptotic expansion of $H_n$, the next one of which is

$$H_n \approx \ln n + \gamma + \frac{1}{2n}.$$

Using this extra term gives an approximation of

$$150 \left( \ln 150 + \gamma + \frac{1}{2 \cdot 150} \right) = 838.677\color{red}{6} \dots $$

which agrees with the exact answer $150 H_{150} = 838.677\color{red}{1} \dots$ to $6$ digits. Of course there's probably no point in getting more than $3$ digits of accuracy.

Answer 2

In @QiaochuYuan's answer, technical details have been nicely discussed.

My purpose in posting this answer is to point out that this video should be watched carefully before judging.

I include some related screenshots below so that members who do not have enough time to watch the whole video will not make a hasty judgment about this teacher.

Numberphile presents and solves the problem beautifully and tries to avoid complicated details. Obviously, at this elementary level, students cannot be taught what Euler's constant is or what other harmonic-number approximations are, and in my opinion, Numberphile's strategy for teaching this topic is very creative.

Using the lower bound

$$nH_n \ge n\log n$$

Numberphile wants to show how non-linearly the expected value increases as $n$ increases by comparing the exact value for $n=3$ with those obtained from the lower bounds for $n=150$ and $n=1025$. Indeed the following asymptotic relation (see the third image):

$$nH_n\sim n\log n$$

is correct in the sense that $\lim_{n\to \infty}\frac{nH_n}{n\log n}=1$.

As you can see from the first image (top left in a desktop preview), Numberphile initially states

The average of or expected total number of encounters is going like $n$ times this $n$th harmonic number, but now what do the harmonic numbers grow like, how big is this going to get as we increase $n$.

Next, Numberphile derives the lower bound, which can be seen in the second image (compare the times). Numberphile also clearly states that it is a very much lower estimate (see the fourth image).

I conclude that if a student watches the video carefully, there is nothing wrong or misdealing, especially considering the elementary level of education, because the numbers are called estimates and minimum, and the purpose of using the lower bound $n\log n$ is to derive the growth rate of the expectation. It should also be mentioned that Numberphile could have improved the video by providing exact harmonic number values ​​to avoid any misunderstandings.

Hope it is helpful!