Will the walker return?

George Pólya answered this in 1921. On a line (one dimension) or a grid of streets (two dimensions), the walker returns home with probability 1 — in fact infinitely often. In three dimensions she does not: the chance of ever coming home is only about $0.34$. A remark often attributed to Shizuo Kakutani puts it this way: a lost person will find their way home, but a lost bird may not.

The reason is a sum. A walk returns home infinitely often exactly when the expected number of visits home is infinite, and that expected number is the sum, over all times, of the chance of being home then. After $2n$ steps the chance of being home behaves roughly like

$$\frac{1}{\sqrt{\pi n}} \;\text{(on a line)}, \qquad \frac{1}{\pi n} \;\text{(on a grid)}, \qquad \text{a constant} \times n^{-3/2} \;\text{(in space)}.$$

The first two sums diverge — the second only just, like the harmonic series — so the walker comes home again and again. The third converges, so she may wander off for ever.

There is a surprise even in one dimension: the walker is certain to return, yet the average time she takes to return is infinite. Random walks like these model the diffusion of molecules, stock prices, the spread of heat, and the search patterns of animals.