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 walk returns almost every time: a classical identity says the probability of not having returned within the first $n$ steps is exactly $\binom{n}{n/2}/2^{n} \sim \sqrt{2/(\pi n)}$, which is only about $1.5\%$ at $n = 3000$, so the 1D rate sits well above $90\%$. The 2D walk also returns with probability $1$ eventually, but far more slowly: the no-return probability after $n$ steps decays only like $\pi/\ln n$, a logarithmic crawl, so even with the $3000$-step cap a real fraction of 2D walks have not yet come back and the rate settles clearly below the 1D one. The 3D walk is the qualitatively different case: it is transient, and its return probability converges to Pólya’s constant $\approx 0.3405$, landing just below that value because the cutoff drops the rare walks that would have returned later. The 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 almost surely, i.e. with probability $1$) 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 version of the central limit theorem (which estimates the chance of landing on one specific lattice point, not just the spread of the position) 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 (algorithms that sample a distribution by taking random steps through a state space) 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.