Pólya's recurrence theorem

Remarks

The walk is a Markov chain, and the origin is recurrent if and only if $\sum_{n} P(S_{2n} = 0) = \infty$. For $d = 1$, $P(S_{2n} = 0) = \binom{2n}{n} 4^{-n}$, which behaves like $(\pi n)^{-1/2}$. For $d = 2$, $P(S_{2n} = 0) = \left(\binom{2n}{n} 4^{-n}\right)^2$, which behaves like $(\pi n)^{-1}$, so the sum still diverges. For general $d$, $P(S_{2n} = 0)$ is of order $n^{-d/2}$, and the sum converges for $d \ge 3$. In dimension $3$, the probability of return is about $0.34$. In dimensions $1$ and $2$ the walk returns infinitely often, and in dimension $d \ge 3$ it satisfies $\abs{S_n} \to \infty$ almost surely.

Going deeper

For a student

The proof reduces recurrence to the divergence of the expected number of returns, which local limit estimates for $P(S_{2n} = 0)$ settle. Another proof views the lattice as an electrical network: the walk is recurrent if and only if the effective resistance from the origin to infinity is infinite. The same dichotomy between $d \le 2$ and $d \ge 3$ appears for Brownian motion, which is neighbourhood recurrent in the plane and transient in $\R^3$.