Random Walk Return Probability in One, Two and Three Dimensions

A simple random walk returns to its start with certainty in one and two dimensions, but only about 34 percent of the time in three dimensions.

A simple random walk on the integer lattice that steps to each of its nearest neighbors with equal probability returns to its starting point with certainty in one dimension and in two dimensions, and returns with probability only about 34 percent in three dimensions. This shift from certain return to a strictly less than certain return, first proven rigorously by George Polya, is one of the cleanest illustrations in probability of how dimensionality changes the qualitative behavior of a process, a change deeper than the numbers alone suggest.

Consider a walker on the integers who, at each time step, moves one unit left or one unit right, each with probability one half, independently at every step. In two dimensions, at each step the walker moves one unit in one of the four compass directions, each with probability one quarter. In three dimensions, the walker moves one unit along one of six directions, each with probability one sixth. In every case the walker starts at the origin, and the question asks for the probability that the walker returns to the origin at some finite time, not necessarily the very next step.

The standard technique avoids trying to compute the return probability directly and instead works with the probability of being exactly at the origin after 2n steps, since an odd number of steps can never return the walker to the origin on a lattice where each step changes parity. Call this quantity u of 2n. A walk is called recurrent, meaning it returns to the origin with probability 1, exactly when the infinite sum of u of 2n over all n diverges. If that sum converges to a finite value instead, the expected total number of visits to the origin is finite, and the walk is called transient, returning with probability strictly less than 1.

In one dimension, u of 2n equals the number of paths of length 2n that return to 0, which is the central binomial coefficient divided by 2 to the power 2n. By Stirling's approximation this behaves like a constant divided by the square root of n. Summing 1 divided by the square root of n over all n diverges, since it decays slower than 1 divided by n, so the one-dimensional walk is recurrent: it returns to the origin with probability exactly 1.

In two dimensions, the walk decomposes along diagonal coordinates into two independent one-dimensional walks, and u of 2n behaves like a constant divided by n. The sum of 1 divided by n over all n is the harmonic series, which also diverges, though only barely, logarithmically rather than at the square root rate of the one-dimensional case. The two-dimensional walk is therefore also recurrent, returning with probability exactly 1, even though its per-step return probability shrinks faster than in one dimension.