Random Walk
A random walk is a stochastic process built by accumulating independent random increments:
where each is drawn i.i.d. from some distribution. The defining character of a random walk is that the past is irrelevant — the conditional distribution of given the entire history depends only on the current position . This is the Markov property, and it is not a coincidence: a random walk is the simplest discrete-time Markov chain on .
The symmetric random walk
The canonical discrete case draws each step from with equal probability:
This is the symmetric (simple) random walk on . Every sample path is a sequence of coin-flip-driven steps on the integer line.
Mean and variance
Because the increments are i.i.d. with and , and because is their sum:
More generally, for increments with variance :
The standard deviation grows as , not . This sub-linear spread is the hallmark of a random walk — the process diffuses outward, but much slower than a deterministic linear trend.
| 1 | 0 | |
| 4 | 0 | |
| 9 | 0 | |
| 100 | 0 | |
| 10,000 | 0 |
The variance grows without bound. A random walk is therefore non-stationary — its distribution changes with time even though its mean stays fixed at zero.
Why non-stationarity matters for time series
A covariance-stationary process requires finite, time-invariant variance. A random walk has variance , so it violates this requirement. This is precisely the unit-root non-stationarity that the Augmented Dickey-Fuller test is designed to detect: the AR(1) model (i.e. ) is a random walk.
The Markov property in detail
A process satisfies the Markov property when:
For a random walk this is immediate: , and is independent of everything before time . So the full history collapses to the current position. This makes random walks analytically tractable — the -step transition probabilities can be computed by convolving the single-step distribution times.
The reflection principle and first-passage times
A powerful tool for symmetric random walks is the reflection principle: any path that reaches level by time can be reflected about after the first hitting time to produce a bijection with paths above at time .
Split the paths that touch by where they finish. Those ending strictly above must have touched it, contributing . Those ending strictly below reflect (mirror the path about after its first hitting time) onto exactly the paths ending above , contributing another . Those ending exactly at are their own mirror image, so they contribute once, not twice. The exact lattice statement is therefore:
The form usually quoted, , is the Brownian motion version: for a continuous process , so the boundary term vanishes. On the integer lattice it does not. When and share parity the shortcut overstates the hitting probability badly — at it claims against the true . The trace below enumerates the full joint law of (position, running max) and checks both forms against it.
The first-passage time for a symmetric walk satisfies:
The expected first-passage time is — a symmetric random walk will almost surely return to any level eventually, but the expected wait is infinite.
Almost sure recurrence
A 1D and 2D symmetric random walk are recurrent: they return to the origin (and every previously visited site) with probability 1. In 3D and higher dimensions the walk is transient — it escapes to infinity and returns to any fixed point with probability less than 1. This dimension threshold is Pólya's theorem (1921).
The Gambler's Ruin
A classic application: a gambler starts with chips, wins or loses one chip per round with probabilities and , and stops when they reach chips (win) or 0 chips (ruined).
Let be the probability of ruin starting from . The Markov property gives the recurrence:
Solving this linear recurrence:
Worked example: , ,
A slight disadvantage ( vs ) at table limit turns a 10-chip bankroll into a near-certain ruin. With (fair game), — still 90% ruin probability with only 10% of the target.
Brownian motion as the continuous limit
Scale a symmetric random walk so that each step covers in time . As with fixed, the Central Limit Theorem drives the distribution of to:
The resulting continuous-time limit is Brownian motion (Wiener process) , characterised by:
- almost surely.
- Independent increments: for .
- Gaussian increments: .
- Continuous paths: almost surely is continuous everywhere, yet differentiable nowhere.
The nowhere-differentiable property means Brownian motion has infinite variation on any interval, which is why its calculus (Itô calculus) requires new rules that do not reduce to ordinary calculus.
| Property | Random Walk | Brownian Motion |
|---|---|---|
| State space | ||
| Time | Discrete | Continuous |
| Increment distribution | Symmetric Bernoulli | |
| Paths | Piecewise constant | Continuous, nowhere differentiable |
| Recurrence (1D) | Yes (Pólya) | Yes |
Drift and the random walk with drift
Adding a constant per step gives a random walk with drift:
When , the process still has variance (still non-stationary), but now wanders in a direction. In the AR(1) framework:
where is the drift term. This is the "random walk with constant" null in the ADF test (regression="c"). The drift does not restore stationarity — only differencing removes the unit root.
A worked path trace: 10 steps
Starting at , draw 10 coin flips:
| 0 | — | 0 |
| 1 | +1 | 1 |
| 2 | −1 | 0 |
| 3 | +1 | 1 |
| 4 | +1 | 2 |
| 5 | −1 | 1 |
| 6 | −1 | 0 |
| 7 | +1 | 1 |
| 8 | +1 | 2 |
| 9 | +1 | 3 |
| 10 | −1 | 2 |
Net displacement . Actual at is , so ending at is unremarkable — the walk could plausibly end anywhere from roughly to .
Stepping the whole distribution at once
A single path tells you what one walk did. The trace below steps the entire law forward instead: it carries the joint distribution of and pushes every state through the same two-branch update. Because it enumerates rather than samples, every number below is exact. There is no Monte Carlo error to hide behind.
Random walk — the exact law, step by step
The whole distribution starts as one atom: the walk is at 0, and the highest level it has ever reached is also 0. Every frame below is the exact law over all 2^t sign sequences at once — no sampling.
A forward DP over the joint law of (position, running maximum). Nothing is sampled, so Var(S_t) = t holds exactly, the reflection principle can be checked instead of assumed, and switching on absorbing barriers turns the same loop into Gambler's Ruin.
What to notice:
- Frame 2 replays the ten hand-worked flips above through the update rule, and shows why the running max rides along for free: it is just a second coordinate of the state.
- Frames 3–5 show the parity constraint. At even only even sites carry mass, at odd only odd ones — the lattice walk can never be found at an unreachable site, a feature Brownian motion loses in the continuum limit.
- Frame 7 reads off the exact law at : it equals to six decimals every time, and . This is the variance table above, verified rather than derived.
- Frame 8 is the reflection-principle check. The exact from the joint law matches for every , while the Brownian shortcut overstates it by up to — precisely , and only when and share parity.
- Frame 9 absorbs at to get the first-passage law. It reproduces exactly, and the cumulative column shows why : after 20 steps 17.6% of paths still have not touched , and after 40 steps 12.5% still have not — the tail only shrinks by a factor of when the horizon doubles, which is exactly slow enough to make the mean diverge.
- Frame 10 is the payoff. Absorb at both and and the same loop becomes Gambler's Ruin, matching the closed form to six decimals, and showing that the same edge is not worth the same to every bankroll. From a edge is exactly symmetric ( vs around ), because makes the half-target case self-symmetric. From it is not: losing adds only to a ruin probability already at , while gaining removes — a larger move. The short stack has no headroom left to lose, and a favourable edge is precisely what buys it the runway to build some.
Applications in machine learning
MCMC and the Metropolis-Hastings algorithm
Markov Chain Monte Carlo methods sample from distributions by constructing a Markov chain whose stationary distribution is . The Metropolis-Hastings algorithm proposes new states via a random walk kernel:
and accepts with probability . The step size controls the trade-off between exploration and acceptance rate — too large and almost every proposal is rejected; too small and the chain explores slowly.
Diffusion models
Score-based and DDPM diffusion models frame image generation as the reverse of a random walk (actually a forward SDE). The forward process gradually corrupts an image over steps:
which in the limit becomes Brownian motion on image space. A neural network is trained to reverse this diffusion (denoising each step) and generation is the reverse walk from pure noise back to a sample.
Random exploration in reinforcement learning
In policy-gradient and Q-learning algorithms, the agent needs to explore state space. A simple exploration strategy is -greedy with random tie-breaking, but more principled approaches explicitly inject random walk noise (e.g., Ornstein-Uhlenbeck process in DDPG) so that exploration is temporally correlated — the agent takes a few random steps in one direction before reversing, covering the state space more efficiently than pure white noise.
Implementing a random walk in NumPy
import numpy as np
import matplotlib.pyplot as plt
rng = np.random.default_rng(42)
def random_walk_1d(n_steps, n_paths=1, sigma=1.0):
"""Simulate n_paths independent random walks of n_steps steps."""
steps = rng.normal(0, sigma, size=(n_paths, n_steps))
return np.concatenate([np.zeros((n_paths, 1)), np.cumsum(steps, axis=1)], axis=1)
T = 500
paths = random_walk_1d(T, n_paths=50)
# Theoretical ±1 SD band
t = np.arange(T + 1)
sd_band = np.sqrt(t)
# Verify empirical variance matches theory
print(f"Var(S_100) theoretical: {100:.1f}")
print(f"Var(S_100) empirical: {paths[:, 100].var():.2f}")
# → values should be close to 100
# 2D random walk
def random_walk_2d(n_steps):
steps = rng.choice([-1, 1], size=(n_steps, 2)) # axis-aligned
return np.vstack([np.zeros((1, 2)), np.cumsum(steps, axis=0)])
path_2d = random_walk_2d(5000)
print(f"Final position: ({path_2d[-1, 0]:.0f}, {path_2d[-1, 1]:.0f})")
print(f"Distance from origin: {np.linalg.norm(path_2d[-1]):.1f} "
f"(expected ~√{len(path_2d)-1} ≈ {np.sqrt(len(path_2d)-1):.1f})")
# Gambler's ruin probability (analytical formula)
def ruin_prob(k, N, p):
"""Probability of ruin starting at k chips, target N, win prob p."""
q = 1 - p
if abs(p - 0.5) < 1e-10:
return 1 - k / N
r = q / p
return (r**k - r**N) / (1 - r**N)
print("Ruin probabilities (target N=100):")
for k, p in [(10, 0.49), (10, 0.50), (10, 0.51), (50, 0.50)]:
print(f" k={k:2d}, p={p:.2f} → R_k = {ruin_prob(k, 100, p):.4f}")
# Show that RW is non-stationary: variance grows linearly
T = 1000
n_paths = 2000
walks = random_walk_1d(T, n_paths=n_paths)
checkpoints = [1, 10, 50, 100, 500, 1000]
print(f"{'t':>6} {'E[S_t]':>10} {'Var(S_t)':>10} {'Theoretical':>12}")
for t_check in checkpoints:
mean = walks[:, t_check].mean()
var = walks[:, t_check].var()
print(f"{t_check:>6} {mean:>10.4f} {var:>10.2f} {t_check:>12.2f}")
A random walk is not ergodic in the usual sense
Ergodicity requires the time average to converge to the ensemble (population) average. A random walk's time-average position converges to zero for any fixed path, but because the variance grows without bound, paths diverge across the ensemble. Long-run sample statistics computed from a single non-stationary path are not reliable estimators of the underlying process parameters — this is the practical reason stationarity must be established before fitting ARIMA or any classical time-series model.
Related concepts
- Augmented Dickey-Fuller Test: the statistical test that detects when a time series is a random walk (unit-root non-stationarity)
- Diffusion Models: generative models built by learning to reverse a Brownian-motion-like corruption process
- Markov Decision Processes: formalises sequential decision-making; a random-policy agent follows a random walk over the state space
- Hypothesis Testing: the statistical machinery behind the ADF unit-root test