random walk escape

can you escape the origin?

a random walk starts at the origin and never aims. every step is one unit in a direction picked by chance, every direction equally likely. it returns when it lands back on the origin. it escapes if it wanders off and never comes back. whether escape is possible depends only on how many dimensions it has to wander in.

each step: one unit left or right, chance 1/2 each

steps 0 returns 0 max dist 0 distance 0

press play or pick a direction

speed 5/frame

"a drunk man always finds his way home"

P(return) = 1

P(return) is the chance the walk ever comes back. on a line it is 1: the walk is recurrent. the reason: after 2n steps a walk is typically about √n from home, spread over roughly √n spots, so the chance it is standing on the origin right then is about 1/√n.

add those chances over every n and you get the expected number of returns. 1 + 1/√2 + 1/√3 + … never stops growing. if there were any fixed chance of never coming back, each return would be a fresh start with that same chance of being the last, and the returns would run out after a finite number on average. so return is certain.

"a drunk bird always finds its nest"

P(return) = 1

in 2D the walk spreads over a patch about √n by √n, roughly n spots, so the chance of standing on the origin after 2n steps is about 1/n. the sum 1 + 1/2 + 1/3 + 1/4 + … still never stops growing, so the walk is still recurrent. but it grows only like the logarithm of the number of steps. keep that in mind for the experiment below.

"a drunk astronaut may be lost forever"

P(return) ≈ 0.3405

in space the walk spreads over a cube about √n on a side, roughly n^1.5 spots, so the chance of being home after 2n steps is about 1/n^1.5. this time the sum 1 + 1/2^1.5 + 1/3^1.5 + … settles to a finite total: on average a walk comes home only about half a time, ever. finitely many returns on average means some walks never return. the walk is transient: only about 34% ever come back.

it came back this time

P(return) ≈ 0.3405

this walk returned, but most do not. in space the chance of being home after 2n steps falls like 1/n^1.5, fast enough that the chances add up to a finite total: on average a walk comes home only about half a time, ever. about 66% of walks drift away forever. run more walks to see the pattern.

the experiment

run 200 walks in each dimension, 50,000 steps each, and track how many have come home by each step. solid lines are your walks, dashed lines are the theory.

1D 2D 3D

the math

polya's recurrence theorem (1921)

A simple random walk on the integer lattice Z^d (the grid of points whose d coordinates are all whole numbers) is recurrent (returns to the origin with probability 1) if and only if d ≤ 2. For d ≥ 3, the walk is transient (positive probability of never returning).

The key quantity is G(d), the expected number of times the walk visits the origin:

expected visits to origin: G(d) = (1/(2π))^d ∫ dθ₁...dθ_d / (1 − (Σ cos θ_i)/d) return probability: P(return) = 1 − 1/G(d) d = 1: G = ∞ → P = 1 (recurrent) d = 2: G = ∞ → P = 1 (recurrent) d = 3: G ≈ 1.516 → P ≈ 0.3405 (transient) d = 4: G ≈ 1.239 → P ≈ 0.1932 d = 5: G ≈ 1.157 → P ≈ 0.1352 d = 6: G ≈ 1.117 → P ≈ 0.1047

return probability by dimension

why does dimension 3 break everything?

The integral for G(d) measures how "concentrated" the walk is near the origin. In low dimensions, the walk is forced to revisit old territory. In higher dimensions, there are too many directions to wander off in, and the walk disperses.

For d = 3, Watson (1939) evaluated the integral exactly using the gamma function Γ, which extends the factorial to fractions:

G(3) = (√6 / 32π³) · Γ(1/24) Γ(5/24) Γ(7/24) Γ(11/24) ≈ 1.5164

the resistance connection

There is a beautiful analogy to electrical networks. Think of each edge of the lattice as a 1-ohm resistor. The walk is recurrent if and only if the effective resistance from the origin to infinity is infinite.

In 1D, the resistors are in series: resistance grows without bound. In 2D, resistance grows like log(n), still diverging. But in 3D and above, the lattice has enough parallel paths that the effective resistance converges to a finite value. Current can "leak" to infinity, and so can the random walker.

This is why d = 2 is the critical dimension. The chance of being back at the origin after 2n steps shrinks like 1/n in 2D, and the sum of 1/n still diverges, just barely, so the walk returns infinitely often. In 3D it shrinks like 1/n^1.5, and that sum converges.

the quotes

The 1D and 2D results are often attributed to Shizuo Kakutani, who reportedly said: "A drunk man will find his way home, but a drunk bird will find its nest." The 3D extension is a folk addition: "but a drunk astronaut will be lost in space."