random walk escape

can you escape the origin?

steps 0 returns 0 max dist 0 distance 0

press play or pick a direction

5/frame

"a drunk man always finds his way home"
P(return) = 1

in 1D, the random walk is recurrent. no matter how far it wanders, it always returns to the origin. you cannot escape a line.

"a drunk bird always finds its nest"
P(return) = 1

in 2D, the random walk is still recurrent. the plane is not big enough to get lost in. return is certain.

"a drunk astronaut may be lost forever"
P(return) ≈ 0.3405

in 3D, the random walk is transient. only about 34% of walks ever return to the origin. space is big enough to get lost in.

it came back this time
P(return) ≈ 0.3405

this walk returned, but most do not. in 3D, about 66% of walks drift away forever. run more walks to see the pattern.

the experiment

run hundreds of walks in each dimension and watch the return rates converge to their true values.

1D 2D 3D

the math

polya's recurrence theorem (1921)

A simple random walk on the integer lattice Zd 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θ1...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.1050

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 gamma functions:

G(3) = (√6 / 32π³) · Γ(1/4)4 ≈ 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 plane is just barely recurrent: it takes the walk an expected infinite time to return, but it always does.

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."