Probability Question: A lottery has $25$ million participants. Calculate the expected rounds to get to $5$ participants or less

Question

A lottery has 25 million participants. At each round a random number of participants is selected to participate in the next round. That number is uniformly distributed between 1 and the number of participants left. How many round should be expected on average to get to 5 participants or less? The answer should be one of 22, 23, 24, 25.

My idea: Let $n$ be the number of participants left and $f(n)$ be the expected rounds to get to 5 participants or less. Clearly, $f(5) = 0$, $f(6) = 1$,...and $$f(n) = \frac{1}{n}(f(n-1) + f(n-2) + ... + f(5)) + 1 $$ So I coded it in Python and got result 16.16.

Here is my code:

pre_sum = 0 #this is f(5) + f(6) + ... + f(n-1)
for n in range(6, 25000001):
    #calculate f(n)
    temp = pre_sum/n + 1
    #update pre_sum
    pre_sum += temp

The last temp is 16.16.

I have two questions regarding this problem:

1. Why is my method wrong?
2. Are there any ways to compute this question without coding?

Answer 1

$$\frac{25,000,000}{2^k}\leq 5$$

$$k\geq \frac{log5,000,000}{log2}$$

$$k\geq22.26$$

$$k=23$$

Answer 2

Whoever set the question didn't try it out as you did.

The effects are multiplicative, so the effect on the logarithm is additive. On average, the natural logarithm reduces by $1$ at each step. The natural logarithm of $25000000/5$ is 15.4, so 16 steps are needed. Perhaps my calculation has errors because only whole numbers are used.

Answer 3

As far as your method, it is correct and your answer is almost right. There is a slight mistake which I have shown below. With correction, I get 16.5283.

$f(n) = \frac{1}{n}(f(n) + f(n-1) + f(n-2) + ... + f(6)) + 1$

$\frac{n-1}{n} f(n) = \frac{1}{n}(f(n-1) + f(n-2) + ... + f(6)) + 1$

$f(n) = \frac{1}{n-1}(f(n-1) + f(n-2) + ... + f(6)) + \frac{n}{n-1}$

The reason for changes -

i) when $n$ participants are left, you can again randomly pick $n$ participants for the next round with $\frac{1}{n}$ probability.

ii) The game ends when you get any number less than or equal to $5$.

This is the Python script I ran -

pre_sum = 0
temp = 0
for n in range(6, 25000001):
$\space$ pre_sum += temp
$\space$ temp = pre_sum/(n-1) + n/(n-1)
pre_sum = temp
print(pre_sum)