recurrence and transience of the random walk (Polya's theorem)
/ POH-yah /
Set a walker loose to wander randomly, taking independent steps forever. Here is a deceptively simple question with a startling answer: will the walker ever come back home to the starting point? The shocking discovery, due to George Polya in 1921, is that the answer depends entirely on the dimension of the space the walker roams in.
Two outcomes are possible for any state. A walk is recurrent if it returns to its start with probability 1 — and if it does so once for certain, it does so infinitely often. A walk is transient if there is a positive chance it never returns; in that case it makes only finitely many visits and eventually escapes to infinity, never to be seen at the origin again. Polya's theorem says, for the symmetric simple random walk on the integer lattice: in dimension 1 (a line) it is recurrent, in dimension 2 (a grid) it is still recurrent, but in dimension 3 and every higher dimension it is transient. The folk slogan is 'a drunk man finds his way home, but a drunk bird may not'.
The reason is a competition between two effects. The chance of being back at the origin at step n decays roughly like n^(-d/2), where d is the dimension. To decide return, you sum these chances over all n: the sum of n^(-d/2) diverges (giving recurrence) when d is 1 or 2, but converges (giving transience) when d is 3 or more — exactly the boundary at d = 2. In three dimensions there is simply too much room: the walker has so many directions to escape into that the probability of ever returning to a 3D return probability of only about 0.34. Recurrence versus transience is one of the most fundamental classifications of any process, and the random walk is where the distinction first becomes vivid.
On a line, the symmetric walk is recurrent: with probability 1 it returns to 0, in fact infinitely many times — though the expected time until the first return is infinite (it always comes back, but you may wait a very long time). In three dimensions, by contrast, the probability of ever returning to the origin is only about 0.3405; with probability about 0.66 the walker, once it leaves, never sees home again.
Recurrent in 1D and 2D, transient in 3D and up — the dividing line sits exactly at dimension 2.
Recurrent does NOT mean 'returns quickly'. The 1D walk is recurrent yet the expected waiting time to first return is infinite — return is certain but typically very slow. Recurrence is about whether it returns, not how fast.