The drunkard wandering along a sidewalk almost surely returns home. The drunkard wandering across a city almost surely returns home. The bird flying through three-dimensional space, taking unit-length steps in random directions, may never return: there is a positive probability of escaping to infinity, never to come back.

This is Pólya’s recurrence theorem (Pólya, 1921): on the integer lattice $\mathbb{Z}^d$, a simple random walk (each step picks one of the $2d$ unit-vector directions uniformly) returns to the origin with probability $1$ if and only if $d \le 2$.

The phase transition is precisely at $d = 2$. In $d = 3$ the walk returns with probability about $0.3405$, known as Pólya’s constant. The probability shrinks further in higher dimensions.

Three independent walks running in 1D, 2D, and 3D below. The current walk in each panel restarts when it hits the origin (a return) or after $3000$ steps (give up). The counter shows the empirical fraction of walks that have returned.

Watch the rates after a couple of minutes. The 1D and 2D walks should be returning at well above 90% (they will eventually return with probability 1, given enough time; the cap at $3000$ steps is what occasionally lets one slip through). The 3D walk will settle around $60$–$70\%$ — the asymptotic infinite-time limit is $1 - 0.3405 \approx 0.66$, but the $3000$-step cutoff sometimes counts a wandering walk as a non-return when it would have returned eventually. The qualitative split between the dimensions is the result.

The argument

Let $S_n$ denote the position of the walk after $n$ steps. The walk is recurrent (returns to the origin infinitely often a.s.) iff the expected number of returns is infinite:

So the dichotomy reduces to convergence vs. divergence of $\sum_n \Pr[S_n = 0]$.

For the simple symmetric random walk on $\mathbb{Z}^d$, a local central limit theorem gives

with an explicit constant $C_d > 0$. Plugging in,

The series $\sum 1/n^{d/2}$ converges iff $d/2 > 1$, i.e., $d \ge 3$.

So:

• $d = 1, 2$: the series diverges; the walk returns infinitely often (recurrent), and in particular returns at least once with probability $1$.
• $d \ge 3$: the series converges; the walk returns only finitely often (transient), and the probability of never returning is strictly positive.

The precise return probability in $d = 3$ has the closed form

where $u(0,0,0)$ is the value of the lattice Green’s function at the origin:

Watson (1939) evaluated this triple integral in terms of elliptic integrals, getting $u(0,0,0) \approx 1.516$ and so the return probability $\approx 0.3405$.

Where this matters

• MCMC and random-walk Metropolis-Hastings in high-dimensional state spaces are inherently transient unless the chain has a centering force from the target distribution; you cannot rely on diffusive recurrence to revisit important states.
• Resistor networks on $\mathbb{Z}^d$ have effective resistance from the origin to infinity that is finite iff $d \ge 3$. Recurrence is exactly the statement that this resistance is infinite.
• Polymer models behave qualitatively differently in dimension $\le 2$ vs. $\ge 3$, because random-walk-like polymers have very different self-intersection statistics.

References

• George Pólya. Über eine Aufgabe der Wahrscheinlichkeitsrechnung betreffend die Irrfahrt im Straßennetz. Mathematische Annalen, 84(1-2):149-160, 1921.
• G. N. Watson. Three triple integrals. Quarterly Journal of Mathematics, 10:266-276, 1939.
• Frank Spitzer. Principles of Random Walk. Springer, 1976.
• Steven R. Finch. Mathematical Constants. Cambridge University Press, 2003. Section 5.9 on Pólya’s constant.