Gaussian Random Walk

Gaussian random walk

A robot starts at the centre of an 11 × 11 grid and moves by discretised Gaussian steps. The west edge is a pool and the east edge is a pizza. The question is the probability that the robot reaches the pizza before the pool.

Model

State: the cell (x, y), 121 states in total.
Action: a single action, wander.
Step: an offset (dx, dy) with each component in −2 to 2, with weight proportional to exp(−((dx − wind)² + dy²) / 2σ²) and σ = 1. Positions are clipped at the north and south edges.
Terminal states: the column x = 0 (pool) and the column x = 10 (pizza).
Reward: 1 on arrival at the pizza, otherwise 0. Discount factor: 1.

With these rewards, the value of a cell equals the probability of reaching the pizza first from that cell. evaluate computes it by solving one linear system.

import aniate as an
from plane import gaussian_plane, pizza_probability

calm = gaussian_plane()
calm.initial @ calm.evaluate(None)                              # 0.5
an.simulate(calm, None, episodes=20_000, seed=1).mean_return    # 0.491, standard error 0.0035

windy = gaussian_plane(drift=0.3)
windy.initial @ windy.evaluate(None)                            # 0.9561
runs = an.simulate(windy, None, episodes=20_000, seed=1)
runs.mean_return                                                # 0.9551, standard error 0.0015
pizza_probability(windy)                                        # (11, 11) array of exact probabilities

Without wind, the step distribution and the grid are both symmetric under the reflection x ↦ 10 − x. The probability from the centre is therefore exactly 1/2, and the computed value agrees to within 1e-9. A wind of 0.3 cells per step raises the probability to 0.956. The mean walk length is about 17 steps, so the drift accumulates over few steps.

Tests

pytest tests/gaussian

test	property verified
`test_symmetric_gaussian_walk_is_a_fair_coin`	the exact value is 0.5; every sampled return is 0 or 1; the Monte Carlo mean lies within 5 standard errors of 0.5
`test_wind_tilts_the_odds_and_the_martingale_stays_flat`	with wind, 0.9 < P < 1; the mean of the value martingale equals P at every step; `check` passes

Plots

python tests/gaussian/plot.py

file	content
`plane.pdf`	the exact probability for every cell, without and with wind; the square marks the start
`overview.pdf`	for 20,000 walks with wind: the outcome distribution, the running mean, the accumulated return, and the value martingale

The exact probability of reaching the pizza first from every cell, without and with wind; the square marks the start.

For 20,000 walks with wind: the outcome distribution, the running mean, the accumulated return, and the value martingale.

[View the source on GitHub]