How many times must a bounded random number generator bounded by its output run until it outputs 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