Random WalkOpen in Colab

Random Walk

A random walk is a stochastic process {St}t≥0\{S_t\}_{t \ge 0} built by accumulating independent random increments:

St=∑i=1tεi,S0=0,S_t = \sum_{i=1}^{t} \varepsilon_i, \qquad S_0 = 0,

where each εi\varepsilon_i 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 St+1S_{t+1} given the entire history depends only on the current position StS_t. This is the Markov property, and it is not a coincidence: a random walk is the simplest discrete-time Markov chain on R\mathbb{R}.

The symmetric random walk

The canonical discrete case draws each step from {−1,+1}\{-1, +1\} with equal probability:

εi={+1with probability 12−1with probability 12\varepsilon_i = \begin{cases} +1 & \text{with probability } \tfrac{1}{2} \\ -1 & \text{with probability } \tfrac{1}{2} \end{cases}

This is the symmetric (simple) random walk on Z\mathbb{Z}. 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 E[εi]=0\mathrm{E}[\varepsilon_i] = 0 and Var(εi)=1\mathrm{Var}(\varepsilon_i) = 1, and because StS_t is their sum:

E[St]=0,Var(St)=t.\mathrm{E}[S_t] = 0, \qquad \mathrm{Var}(S_t) = t.

More generally, for increments with variance σ2\sigma^2:

Var(St)=tσ2.\mathrm{Var}(S_t) = t\sigma^2.

The standard deviation grows as t\sqrt{t}, not tt. This sub-linear spread is the hallmark of a random walk — the process diffuses outward, but much slower than a deterministic linear trend.

ttE[St]\mathrm{E}[S_t]SD(St)=σt\mathrm{SD}(S_t) = \sigma\sqrt{t}
10σ\sigma
402σ2\sigma
903σ3\sigma
100010σ10\sigma
10,0000100σ100\sigma

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 =tσ2→∞= t\sigma^2 \to \infty, 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 yt=yt−1+εty_t = y_{t-1} + \varepsilon_t (i.e. ϕ=1\phi = 1) is a random walk.

The Markov property in detail

A process {St}\{S_t\} satisfies the Markov property when:

P(St+1=s∣S0,S1,…,St)=P(St+1=s∣St).P(S_{t+1} = s \mid S_0, S_1, \ldots, S_t) = P(S_{t+1} = s \mid S_t).

For a random walk this is immediate: St+1=St+εt+1S_{t+1} = S_t + \varepsilon_{t+1}, and εt+1\varepsilon_{t+1} is independent of everything before time t+1t+1. So the full history collapses to the current position. This makes random walks analytically tractable — the kk-step transition probabilities can be computed by convolving the single-step distribution kk times.

The reflection principle and first-passage times

A powerful tool for symmetric random walks is the reflection principle: any path that reaches level a>0a > 0 by time tt can be reflected about aa after the first hitting time to produce a bijection with paths above aa at time tt.

Split the paths that touch aa by where they finish. Those ending strictly above aa must have touched it, contributing P(St>a)P(S_t > a). Those ending strictly below aa reflect (mirror the path about aa after its first hitting time) onto exactly the paths ending above aa, contributing another P(St>a)P(S_t > a). Those ending exactly at aa are their own mirror image, so they contribute P(St=a)P(S_t = a) once, not twice. The exact lattice statement is therefore:

P ⁣(max⁡0≤s≤tSs≥a)=2 P(St>a)+P(St=a).P\!\left(\max_{0 \le s \le t} S_s \ge a\right) = 2\,P(S_t > a) + P(S_t = a).

The form usually quoted, 2 P(St≥a)2\,P(S_t \ge a), is the Brownian motion version: for a continuous process P(Wt=a)=0P(W_t = a) = 0, so the boundary term vanishes. On the integer lattice it does not. When aa and tt share parity the shortcut overstates the hitting probability badly — at t=12, a=2t = 12,\ a = 2 it claims 0.7740.774 against the true 0.5810.581. The trace below enumerates the full joint law of (position, running max) and checks both forms against it.

The first-passage time Ta=min⁡{t:St=a}T_a = \min\{t : S_t = a\} for a symmetric walk satisfies:

P(Ta=t)=at P(St=a),t≥a, t≡a(mod2).P(T_a = t) = \frac{a}{t}\,P(S_t = a), \qquad t \ge a,\ t \equiv a \pmod{2}.

The expected first-passage time is E[Ta]=∞\mathrm{E}[T_a] = \infty — 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 kk chips, wins or loses one chip per round with probabilities pp and q=1−pq = 1 - p, and stops when they reach NN chips (win) or 0 chips (ruined).

Let RkR_k be the probability of ruin starting from kk. The Markov property gives the recurrence:

Rk=p Rk+1+q Rk−1,R0=1, RN=0.R_k = p\,R_{k+1} + q\,R_{k-1}, \qquad R_0 = 1,\ R_N = 0.

Solving this linear recurrence:

Rk={(q/p)k−(q/p)N1−(q/p)Np≠q1−kNp=q=12R_k = \begin{cases} \dfrac{(q/p)^k - (q/p)^N}{1 - (q/p)^N} & p \ne q \\[8pt] 1 - \dfrac{k}{N} & p = q = \tfrac{1}{2} \end{cases}

Worked example: k=10k = 10, N=100N = 100, p=0.49p = 0.49

qp=0.510.49≈1.0408\frac{q}{p} = \frac{0.51}{0.49} \approx 1.0408 R10=(1.0408)10−(1.0408)1001−(1.0408)100=1.492−54.61−54.6=−53.1−53.6≈0.991R_{10} = \frac{(1.0408)^{10} - (1.0408)^{100}}{1 - (1.0408)^{100}} = \frac{1.492 - 54.6}{1 - 54.6} = \frac{-53.1}{-53.6} \approx 0.991

A slight disadvantage (p=0.49p = 0.49 vs p=0.5p = 0.5) at table limit N=100N = 100 turns a 10-chip bankroll into a near-certain ruin. With p=0.5p = 0.5 (fair game), R10=1−10/100=0.90R_{10} = 1 - 10/100 = 0.90 — 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 Δx=σΔt\Delta x = \sigma\sqrt{\Delta t} in time Δt\Delta t. As Δt→0\Delta t \to 0 with t=n Δtt = n\,\Delta t fixed, the Central Limit Theorem drives the distribution of StS_t to:

St→dN(0, σ2t).S_t \xrightarrow{d} \mathcal{N}(0,\, \sigma^2 t).

The resulting continuous-time limit is Brownian motion (Wiener process) WtW_t, characterised by:

  1. W0=0W_0 = 0 almost surely.
  2. Independent increments: Wt−Ws⊥Ws−WrW_t - W_s \perp W_s - W_r for r<s<tr < s < t.
  3. Gaussian increments: Wt−Ws∼N(0, t−s)W_t - W_s \sim \mathcal{N}(0,\, t - s).
  4. Continuous paths: almost surely t↦Wtt \mapsto W_t is continuous everywhere, yet differentiable nowhere.
  Wt∼N(0,t)  \boxed{\;W_t \sim \mathcal{N}(0, t)\;}

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.

PropertyRandom WalkBrownian Motion
State spaceZ\mathbb{Z}R\mathbb{R}
TimeDiscrete t∈Nt \in \mathbb{N}Continuous t≥0t \ge 0
Increment distributionSymmetric BernoulliN(0,Δt)\mathcal{N}(0, \Delta t)
Var(St)\mathrm{Var}(S_t)tttt
PathsPiecewise constantContinuous, nowhere differentiable
Recurrence (1D)Yes (Pólya)Yes

Drift and the random walk with drift

Adding a constant μ\mu per step gives a random walk with drift:

St=μt+∑i=1tεi,E[St]=μt.S_t = \mu t + \sum_{i=1}^{t} \varepsilon_i, \qquad \mathrm{E}[S_t] = \mu t.

When μ≠0\mu \ne 0, the process still has variance tσ2t\sigma^2 (still non-stationary), but now wanders in a direction. In the AR(1) framework:

yt=α+yt−1+εt,y_t = \alpha + y_{t-1} + \varepsilon_t,

where α=μ\alpha = \mu 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 S0=0S_0 = 0, draw 10 coin flips:

ε=(+1, −1, +1, +1, −1, −1, +1, +1, +1, −1)\varepsilon = (+1,\ -1,\ +1,\ +1,\ -1,\ -1,\ +1,\ +1,\ +1,\ -1)
ttεt\varepsilon_tStS_t
0—0
1+11
2−10
3+11
4+12
5−11
6−10
7+11
8+12
9+13
10−12

Net displacement S10=2S_{10} = 2. Actual SD\mathrm{SD} at t=10t = 10 is 10≈3.16\sqrt{10} \approx 3.16, so ending at 22 is unremarkable — the walk could plausibly end anywhere from roughly −6-6 to +6+6.

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 (St, max⁡s≤tSs)(S_t,\ \max_{s \le t} S_s) 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

1/10

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.

python
1from collections import defaultdict
2
3# joint law of (position, running max)
4joint = {(0, 0): 1.0}
5
6for t in range(1, T + 1):
7 nxt = defaultdict(float)
8 for (s, m), pr in joint.items():
9 if s <= lo or s >= hi:
10 # absorbed — stays put
11 nxt[(s, m)] += pr
12 continue
13 up = (s + 1, max(m, s + 1))
14 nxt[up] += pr * p
15 nxt[(s - 1, m)] += pr * (1 - p)
16 joint = nxt
17
18# marginals read straight off the joint
19pos = tally(joint, lambda sm: sm[0])
20run = tally(joint, lambda sm: sm[1])
state
setup
p (step up) → 0.5barriers → nonestates → 1E[S_0] → 0Var(S_0) → 0
P(S_0 = s)
0
1.0000

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 tt only even sites carry mass, at odd tt 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 Var(St)\mathrm{Var}(S_t) off the exact law at t=1,4,9,16,36,100t = 1, 4, 9, 16, 36, 100: it equals tt to six decimals every time, and SD=t\mathrm{SD} = \sqrt{t}. This is the variance table above, verified rather than derived.
  • Frame 8 is the reflection-principle check. The exact P(max⁡≥a)P(\max \ge a) from the joint law matches 2P(St>a)+P(St=a)2P(S_t > a) + P(S_t = a) for every aa, while the Brownian shortcut 2P(St≥a)2P(S_t \ge a) overstates it by up to 0.1930.193 — precisely P(St=a)P(S_t = a), and only when aa and tt share parity.
  • Frame 9 absorbs at a=1a = 1 to get the first-passage law. It reproduces atP(St=a)\frac{a}{t}P(S_t = a) exactly, and the cumulative column shows why E[Ta]=∞\mathrm{E}[T_a] = \infty: after 20 steps 17.6% of paths still have not touched +1+1, and after 40 steps 12.5% still have not — the tail only shrinks by a factor of 2\sqrt{2} when the horizon doubles, which is exactly slow enough to make the mean diverge.
  • Frame 10 is the payoff. Absorb at both 00 and N=100N = 100 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 k=50k = 50 a ±1%\pm 1\% edge is exactly symmetric (0.8810.881 vs 0.1190.119 around 0.5000.500), because Rk(p)+RN−k(1−p)=1R_k(p) + R_{N-k}(1-p) = 1 makes the half-target case self-symmetric. From k=10k = 10 it is not: losing 1%1\% adds only 0.0910.091 to a ruin probability already at 0.900.90, while gaining 1%1\% removes 0.2360.236 — a 2.6×2.6\times 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 p(x)p(x) by constructing a Markov chain whose stationary distribution is pp. The Metropolis-Hastings algorithm proposes new states via a random walk kernel:

x′=x+δ,δ∼N(0,σ2I)x' = x + \delta, \qquad \delta \sim \mathcal{N}(0, \sigma^2 I)

and accepts with probability min⁡ ⁣(1, p(x′)p(x))\min\!\left(1,\ \dfrac{p(x')}{p(x)}\right). The step size σ\sigma 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 x0\mathbf{x}_0 over TT steps:

xt=αˉt x0+1−αˉt ε,ε∼N(0,I),\mathbf{x}_t = \sqrt{\bar\alpha_t}\,\mathbf{x}_0 + \sqrt{1 - \bar\alpha_t}\,\boldsymbol{\varepsilon}, \qquad \boldsymbol{\varepsilon} \sim \mathcal{N}(\mathbf{0}, \mathbf{I}),

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 ε\varepsilon-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

Python
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
Python
# 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})")
Python
# 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}")
Python
# 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

Concept neighbourhood

How this concept connects — click any node to jump there, or explore the whole concept map.

RelatedReferenced by
Random WalkThe Augmented Dickey-Full…Hypothesis Testing: Null,…Markov Decision ProcessesDiffusion Models