Probability Question: A lottery has $25$ million participants. Calculate the expected rounds to get to $5$ participants or less 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:

*

*Why is my method wrong?

*Are there any ways to compute this question without coding?

 A: 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)
A: $$\frac{25,000,000}{2^k}\leq 5$$
$$k\geq \frac{log5,000,000}{log2}$$
$$k\geq22.26$$
$$k=23$$
A: 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.
