Is this a random-walk problem?

Question

a simple game has 20 levels (level 1 to level 20):

you start at level 1.

you advance 1 level if you successes, and go back 1 level if you failed (the lowest level is level 1).

the probability of success/fail of each level is 50% (in 1 trial).

now you've given 100 trials, what is your probability of beat the game (went through all 20 levels in 100 trials)?

It is complicated than it looks, I didn't have good intuition on this problem, so I ran a Monte Carlo simulation on this, the result is around 8.14%

can anybody provide a mathematical explanation of this problem? Thanks!

My python code:

import random

NUM_CHANCES = 100  # Total chances
NUM_LEVELS = 20  # Number of levels
PROB_SUCCESS = 0.5  # Probability of success at each level
NUM_SIMULATIONS = 1000000  # Number of simulations


def simulate():
    level = 1  # Start at level 1
    for _ in range(NUM_CHANCES):
        if random.random() < PROB_SUCCESS:  # Success, move up
            level += 1
            if level > NUM_LEVELS:  # Beat the game!
                return True
        else:  # Failure, move down
            level -= 1
            level = max(1, level)  # Can't go below level 1
    return False  # Didn't beat the game


successes = 0
for sim in range(NUM_SIMULATIONS):  # Run simulations
    if simulate():
        successes += 1

probability = successes / NUM_SIMULATIONS
print(f"Probability of beating the game: {probability:.4f}")

Output:

Probability of beating the game: 0.0813
Probability of beating the game: 0.0815
Probability of beating the game: 0.0814

Answer 1

Let $X_t$ be the level in which you are at trial $t$. Since you start at level $1$, $X_0 = 1$. Also, you know that:

• $\mathbb{P}(X_{t + 1} = 2 \mid X_t = 1) = \mathbb{P}(X_{t + 1} = 1 \mid X_t = 1) = \frac{1}{2}$,
• $\mathbb{P}(X_{t + 1} = i - 1 \mid X_t = i) = \mathbb{P}(X_{t + 1} = i + 1 \mid X_t = i) = \frac{1}{2}$ for all $i \in \{ 2, \ldots, 19 \}$,
• $\mathbb{P}(X_{t + 1} = 20 \mid X_t = 20) = 1$ (we say that once you have reached level 20, you stay in this level).

Your goal is to find $\mathbb{P}(X_{100} = 20)$.

Define $\mu_t \in \mathbb{R}^{20}$ such that the $i$-th element of $\mu_t$ is $\mathbb{P}(X_t = i)$. We know that $$\mathbb{P}(X_{t + 1} = i) = \sum_{j = 1}^{20} \mathbb{P}(X_{t + 1} = i \mid X_t = j) \mathbb{P}(X_t = j).$$ Hence, $\mu_{t + 1} = P \mu_t$ where $P$ is the $20 \times 20$ matrix such that $P_{i, j} = \mathbb{P}(X_{t + 1} = i \mid X_t = j)$.

Then, remark that $\mu_{100} = P \mu_{99} = P^2 \mu_{98} = \ldots = P^{100} \mu_0$ and, since you know that $X_0 = 1$, what you need to compute is $$\mu_{100} = P^{100} \mu_0 \qquad \text{with} \qquad P = \begin{pmatrix} \frac{1}{2} & \frac{1}{2} & 0 & 0 & \ldots & 0 \\ \frac{1}{2} & 0 & \frac{1}{2} & 0 & \ldots & 0 \\ 0 & \ddots & \ddots & \ddots & \ddots & \vdots \\ \vdots & \ddots & \frac{1}{2} & 0 & \frac{1}{2} & 0 \\ 0 & \ldots & 0 & \frac{1}{2} & 0 & 0 \\ 0 & \ldots & 0 & 0 & \frac{1}{2} & 1 \end{pmatrix} \qquad \text{and} \qquad \mu_0 = \begin{pmatrix} 1 \\ 0 \\ \vdots \\ 0 \end{pmatrix}.$$