What is the expected score of this game?

Question

Construct a non-increasing sequence of integers between 0 and 9 by doing the following:

1) Draw a random integer between 1 and 9. Call this $X_1$. Multiply this number by $10^{-1}$.

2) To the result of the previous step, add a random integer between 0 and $X_1$ inclusive. Call this $X_2$. If you draw 0, the sequence terminates. If your draw is not 0, then multiply $X_2$ by $10^{-2}$ and add this to the result of previous step.

3) Repeat until 0 is drawn, all the while multiplying draws by successively smaller powers of 10.

So, for example, I could draw 6 as my first number, 3 as my second number, 3 as my third number, 1 as my fourth number, and 0 as my fifth number. The result would be 0.6332 (or $\sum_{i = 1} X_i10^{-i}$).

What is the expected value of this sequence? Can it be computed analytically? If so, how?

Here is some python code to simulate this:

import numpy as np 

def sim():

    last_draw = 0
    while last_draw==0:
        last_draw = np.random.randint(low=0, high=10)

    digits = [last_draw]
    while last_draw!=0:
        last_draw = np.random.randint(low=0, high=last_draw+1)
        digits.append(last_draw)

    digits = np.array(digits)
    tens = 10.0**(-np.arange(1,len(digits)+1))

    return np.dot(digits, tens)

if __name__=='__main__':

    sims = [sim() for j in range(100000)]

    print(np.mean(sims))

Answer 1

Let's $\mu_k$ be the expected value after we draw $k$, and $\mu$ be the total expected value of the game. Then, since we draw between 1 and 9 in the beginning: $$\mu=\frac{1}{90}\sum_{k=1}^9(k+\mu_k)$$

If we have $k$, where $k>0$, at the last draw, we can write the expected value of our next draws as: $$\mu_k=\frac{1}{10(k+1)}\sum_{i=1}^k(i+\mu_i)\rightarrow\mu_k=\frac{k(k+1)}{2(10k+9)}+\frac{1}{10k+9}\sum_{i=1}^{k-1}\mu_i$$ Via inductive logic and some algebra, you'll see that this recursion has the solution $\mu_k=k/19$ (substitute it), yielding $\mu=10/19\approx 0.526..$.