# Expected Number of Trials to Terminate Random Sequence

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.

• While editing, I didn't change your symbols, but I presume you're asking $E[s]$, which the title asks. Jun 13, 2020 at 19:12

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$$.