Expected Number of Trials to Terminate Random Sequence

Question

I recently encountered this question and I'm having difficulty coming up with a rigorous explanation to back up the intuitive answer.

Let $R$ be a random number generator such that $R(n)$ returns an integer in the range $[0, 1, ..., n-1]$ with uniform probability. Starting from $x_0=N$, consider the sequence $x_i=R(x_{i-1})$. Eventually the sequence terminates at $x_s=0$ for some $s$ and no further generation is possible. What is $\mathbb{E}[s]$?

For large $N$, I can see that intuitively the answer is approximately $\log_2N$, since $\mathbb{E}[x_{i+1}]\approx x_i/2$ and after $\log_2N$ trials, on average we should be left with some value close to 0. I'm not sure how to come up with a more rigorous method to prove this and find a more precise answer.

Answer 1

Let $E_n$ be the expected number of trials if the starting number is $n$. Then, $$E_n=1+\frac{1}{n}\sum_{i=1}^{n-1} E_i$$

Via some algebraical manipulations, you'll have $$E_{n}=E_{n-1}+\frac{1}{n}\rightarrow E_n=\sum_{i=1}^n\frac{1}{i}$$ So, it's not $\log_2n$.