How many times must a bounded random number generator bounded by its output run until it outputs 1?

Question

Say you have a function with input $x$ that generates a random integer between $1$ and $x$. Every time you run the function you replace its input with its output until the function outputs $1$. What is the expected number of times you will have to run the function?

For example, if $x$ is $1000$. You run $f(1000)$ and it gives you, say $500$. Then you run $f(500)$ and it gives you $1$. So it took you $2$ runs to roll a $1$, I was wondering what the expected amounts of runs would be for $x$.

I initially thought it would just be $\log_2x$ because you are expected to halve the value on each run, but that clearly doesn't work for $x=2$ because you're expected to roll twice to get $1$. Maybe that's just because its a base case so I wrote this on python to check for 1000 -

y = 0
for j in range(100000):
    i = 1000
    z = 0
    while i>1:
        i = randrange(1, i+1)
        z+=1
    y += z
y = y/100000
print(y)

and it gives approximately ~8.5 rolls. Any ideas?

Answer 1

Let $\mathbb{N}$ refer to the positive integers.

Let $l$ be a function from $\mathbb{N}$ to $\mathbb{R}$ representing the expected number of turns needed to reach $1$.

We can tell from your example that the integer range $1 \cdots x$ is inclusive. For example, if the value at turn $t$ is $100$, the value at turn turn $t+1$ can be $100$.

If the value on turn $t$ is $x$, then every integer $\{1,2,\cdots x\}$ is equally likely to be the value on the next turn.

This process has no memory, so if our state is $50$, the expected number of turns remaining does not depend on the number of turns that have already passed.

With this, we can give a group of equations that holds for all $n$. We will temporary not address the issue of a base case.

$$ l(n) = 1 + \frac{1}{n}\sum_{i=1}^nl(i)$$

Let's define a helper function $L$ representing the number of turns left not counting the current one.

$$ L(n) = \frac{1}{n}\sum_{i=1}^nl(i) $$

Hence, the following holds

$$ l(n) = 1 + L(n) $$ $$ n \cdot l(n) = n + n \cdot L(n) $$ $$ n \cdot l(n) = n + l(n) + (n-1)\cdot L(n-1) $$ $$ (n-1)\cdot l(n) = n + (n-1) \cdot L(n-1) $$ $$ l(n) = \frac{n}{n-1} + L(n-1) $$ $$ l(n) = \frac{n}{n-1} + l(n-1) - 1$$ $$ l(n) - l(n-1) = \frac{n}{n-1} - 1 $$ $$ l(n) - l(n-1) = \frac{n-(n-1)}{n-1} $$ $$ l(n) - l(n-1) = \frac{1}{n-1} $$

Let's note that, because of how $l$ is defined, successive differences of $l$ are the same as successive differences of $L$.

Now that we have a nice formula for the difference between successive values of $L(n)$, we just need a base case.

$$ L(1) = 0 \;\;\;\text{and}\;\;\; L(2)-L(1) = 1 $$

$$ L(n) = \sum_{i=1}^{n-1} \frac{1}{i} $$

And therefore, as desired:

$$ l(n) = 1 + \sum_{i=1}^{n-1} \frac{1}{i} $$

$l(1000)$ is indeed approximately $8.5$.

>>> 1 + sum(1/x for x in range(1, 1000))
8.484470860550342

Answer 2

Let $X_n$ be the random variable representing the amount of time taken to get to $1$ and let $f(n)=\mathbb{E}[f_n]$. We know that $f(1)=1$. In general, if we start with $n$, then with probability $\frac{1}{n}$ we roll $n$ and end up back where we started except we've made one roll. If we roll $1<m<n$, then the expectation in this case is $1+f(m)$ since it's as if we began with $m$ initially expect we've made an extra roll. By the law of total expectation, this means that if $A_i$ is the event "the first roll is $i$" then: $$f(n)=\mathbb{E}[f(n)\mid A_n]P(A_n)+\mathbb{E}[f(n)\mid A_{n-1}]P(A_{n-1})+\cdots +\mathbb{E}[f(n)\mid A_1]P(A_1)=\\ \frac{1}{n}[(f(n)+1)+(f(n-1)+1)+\cdots (f(2)+1)+1]= \frac{1}{n}(f(n)+f(n-1)+\cdots +f(2)+n)$$ which implies that $$f(n)=\frac{1}{n-1}(f(n-1)+\cdots+f(2)+f(1) + (n-1))$$ You can use this to iteratively compute $f(n)$, but I am not sure if there is a closed form expression.