THE RANDOM WALK Polya: lost in 1D and 2D, free in 3D
The simple symmetric random walk steps ±1 with equal probability. Polya's 1921 theorem draws a hard line by dimension: in one and two dimensions the walk is recurrent — it returns to the origin with probability 1, infinitely often; in three or more it is transient — it wanders off and, with positive probability, never comes back. The test: whether the sum of return-probabilities Σ u₂ₙ diverges.
THE TECHNIQUE recurrent ⇔ Σ u₂ₙ = ∞ ; true in 1D/2D, false in 3D
Accumulate the return-probabilities u₂ₙ = C(2n,n)/4ⁿ for the 1D walk — the partial sum climbs without bound (recurrent) — and compare the 3D walk, whose sum converges to a finite constant (transient): live demo
HISTORY & CREDIT Pearson 1905 · Polya 1921
“A fair random walk always comes back to where it started.” — only in one and two dimensions. In 3D the same fair ±1 walk returns with probability just ≈0.34 and otherwise escapes forever. Recurrence is a property of the dimension, not of fairness. cited
1905 · Karl Pearson — coins the term “random walk” in a one-paragraph letter to Nature asking where a wandering man ends up. 1921 · George Polya — proves the recurrence/transience split at dimension 3 (the Irrfahrt theorem). 1939 · G. N. Watson — evaluates the 3D return probability, ≈0.3405, via a triple integral.
Kakutani's line: a drunk man will find his way home, but a drunk bird may get lost forever. Same fair step, different dimension, opposite fate. Polya 1921
RECOMMEND FOR I-13 the recurrence sum diverges in 1D, computed
On the canonical compiler the partial sum of 1D return-probabilities keeps climbing as the horizon grows — the divergence that is recurrence:
$ i13 run rwalk.i13 # sum of u_2n = C(2n,n)/4^n, 1D symmetric walk
sum to n=50 = 7.117321926851182
sum to n=200 = 15.027360212076687
sum to n=800 = 30.950271589123673 -- unbounded (~2 sqrt(n/pi)) => RECURRENT
Recommend: the random walk is LIT for I-13 — verified the 1D return-probability sum grows 7.12 → 15.03 → 30.95 as the horizon quadruples, tracking 2√(n/π) and diverging, so the origin is recurrent by Polya's criterion. The 3D sum instead converges near 1.516 (return prob ≈0.34) — transient. One ratio recurrence, no random numbers needed.