Random Walk Survival Probability on a Grid

Probability · Medium · Free problem

A particle starts at position $(x_0, y_0)$ on an $8 \times 8$ grid with corners at $(0,0)$ and $(7,7)$. At each time step, it moves to one of its four neighbors (up, down, left, right) with equal probability

/4$. If a move would take the particle outside the grid, it is considered to have exited.

Given a starting position $(x_0, y_0)$ and a number of steps $n$:

  1. What is the probability that the particle stays within the grid for all $n$ steps?
  2. Describe a dynamic programming approach to compute this probability efficiently.
  3. What are the time and space complexities of your method?

Hints

  1. Think of each grid cell as a state. You can track the probability of being at every cell simultaneously and evolve the distribution one step at a time.
  2. At each step, probability mass at $(x,y)$ splits equally among in-bounds neighbors. Mass that would go out of bounds disappears -- that is the exit probability leaking away.
  3. Initialize $p[x_0][y_0] = 1$, iterate the transition $n$ times, and sum the remaining mass. You only need two arrays (current and next) for $O(64)$ space.

Worked Solution

How to Think About It: This is a classic absorbing-boundary random walk. The grid edges act like a cliff -- step off and you are done. The survival probability depends heavily on where you start: a particle at the center $(3,3)$ has much more room to wander than one starting at a corner $(0,0)$. The key structural observation is that the state space is small (only 64 positions), so you can track the full probability distribution over all cells at each time step using a DP table.

Quick Estimate: Consider a particle starting at the center $(3,3)$. In each dimension, the distance to the nearest boundary is 3. For a 1D random walk, the probability of hitting a boundary within $n$ steps falls off roughly as

- O(1/n)$ for large $n$, but for small $n$ the particle is mostly safe. After 1 step from the center, exit probability is 0 (all 4 neighbors are in bounds). After 2 steps, the particle has spread out but is still mostly concentrated near the center. For $n = 10$, survival should still be high -- maybe around 0.85-0.95. For a corner start like $(0,0)$, after just 1 step there is a
/4 = 0.5$ chance of exiting (two of four neighbors are out of bounds), so survival drops fast.

Algorithm:

The idea is to maintain a probability table $p[x][y]$ over all grid cells and evolve it forward one step at a time. At each step, probability mass that would flow off the grid simply vanishes (the particle has exited). After $n$ steps, the total remaining probability mass equals the survival probability.

1. Initialize: set $p[x_0][y_0] = 1$, all other cells to 0. 2. For each time step $t = 1, 2, \ldots, n$: - Create a fresh table $p'[x][y] = 0$ for all $(x,y)$. - For each cell $(x,y)$ in $[0,7]^2$ with $p[x][y] > 0$, distribute $p[x][y]/4$ to each of the four neighbors $(x \pm 1, y)$ and $(x, y \pm 1)$ -- but only if that neighbor is inside $[0,7]^2$. Probability sent to out-of-bounds neighbors is lost. - Replace $p$ with $p'$. 3. After $n$ steps, the survival probability is:

$P(\text{survive } n \text{ steps}) = \sum_{x=0}^{7} \sum_{y=0}^{7} p[x][y]$

Code:

```python def survival_probability(x0, y0, n, grid_size=8): # Initialize probability table p = [[0.0] * grid_size for _ in range(grid_size)] p[x0][y0] = 1.0

directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

for _ in range(n): p_new = [[0.0] * grid_size for _ in range(grid_size)] for x in range(grid_size): for y in range(grid_size): if p[x][y] > 0: for dx, dy in directions: nx, ny = x + dx, y + dy if 0 <= nx < grid_size and 0 <= ny < grid_size: p_new[nx][ny] += p[x][y] / 4.0 # else: probability mass is absorbed (particle exited) p = p_new

return sum(p[x][y] for x in range(grid_size) for y in range(grid_size)) ```

Complexity:

Alternative -- matrix exponentiation: You can encode the transition as a $64 \times 64$ matrix $M$ where $M_{(x',y'),(x,y)} = 1/4$ if $(x',y')$ and $(x,y)$ are adjacent and both in bounds, and 0 otherwise. Then $p^{(n)} = M^n \, p^{(0)}$, and the survival probability is $\mathbf{1}^T M^n p^{(0)}$. This costs $O(G^3 \log n)$ via fast exponentiation, which beats the DP approach when $n$ is very large (since $64^3 \approx 262{,}000$ regardless of $n$).

Answer: The survival probability is the total probability mass remaining on the grid after $n$ DP iterations: $P(\text{survive}) = \sum_{x,y} p[x][y][n]$. The DP runs in $O(64n)$ time and $O(64)$ space. For large $n$, matrix exponentiation gives $O(64^3 \log n)$.

Intuition

This problem illustrates a fundamental technique in stochastic processes: tracking the full probability distribution over a finite state space rather than simulating individual paths. Because the grid is small (64 cells), you can propagate the exact distribution forward cheaply. The absorbing boundary turns this into a "leaky" Markov chain -- probability mass drains out at the edges with every step, and whatever remains is your survival probability. This same framework appears constantly in quant work: pricing barrier options on a lattice, computing default probabilities on a credit grid, or analyzing gambler's ruin problems.

The deeper lesson is about choosing the right representation. You could simulate millions of random walks and estimate the survival probability by Monte Carlo, but that is slow and noisy. The DP approach gives you the exact answer in microseconds because the state space is small enough to enumerate. Recognizing when a problem has a compact state space that you can enumerate exactly -- versus one that requires simulation -- is one of the most valuable skills in quantitative modeling.

Open the full interactive solver →