3
$\begingroup$

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.

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

1 Answer 1

3
$\begingroup$

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

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.