This elegant quote, which captures the essence of the mathematical fact that a 2-dimensional random walk is recurrent while in higher dimensions it is not, is attributed to Shizuo Kakutani. However, the original proof is due to George Pólya [1].

A -dimensional lattice is defined as a graph whose vertices are all points in with integer coordinates. Each vertex is connected to the points that differ from it by exactly one unit along a single coordinate axis, forming the natural grid structure of . With a small Python script, we can visualize these lattices as follows in 2 and 3 dimensions.

George Pólya considered the simple random walk, where the probability of choosing any one of the 2d neighbors of a vertex in the -dimensional grid is . Consider that the random man and bird start their random walks from and respectively. What is the chance that after leaving their initial starting point, they will return to it? If the probability is 1, then the escape probability . In this case, the random walk is called recurring, while in the opposite case transient. Pólya proved the following elegant theorem:

Pólya’s Theorem. A simple random walk on a -dimensional lattice returns to its starting point infinitely often (is recurrent) when or , but has a nonzero probability of never returning (is transient) when .

Several proofs using different machinery are known. A direct proof for using elementary counting techniques and Stirling’s approximation follows. See also [3,4] for a complete treatment, as the discussion below omits some intermediate steps. For a more sophisticated approach involving analytic tools, see [2]. The first key observation is that if is the probability of returning to the starting point, the probability that we have exactly returns is . Therefore, the expected number of visits, including the initial visit when the random walk starts for convenience is : . Observe that when the expected number of visits is , whereas if , or equivalently , then is finite. Notice that if we define to be the probability that the random walk is back at the origin after steps, the expected number of returns is simply . Notice also that for any odd , we have , since returning to the origin requires an equal number of steps in opposite directions along each dimension, which is only possible when is even.

Given that in 2d each node has 4 neighbors, each return in steps has probability . Now we count the number of such paths that involve k steps east, k west, n-k north and n-k south. The number of such paths is: . By summing over all and doing some basic simplifications, we obtain that the probability we care about for an even number of steps , . By using Stirling’s formula it is straight-forward to see that the sum diverges, and thus . On the contrary, the same approach will lead to a convergent summation in 3 dimensions. Specifically, in 3d, the probability of returning to the origin in steps is for some large enough constant . Since and a simple random walk in three dimensions is transient.

References

[1] Pólya, G. (1921). “Über eine Aufgabe der Wahrscheinlichkeitsrechnung betreffend die Irrfahrt im Straßennetz”. Mathematische Annalen.
[2] Pólya’s random walk theorem (MIT notes by Novak)
[3] Notes from Princeton (page 43)
[4] Random walks and electric networks by Doyle and Snell