Pólya's Recurrence Theorem

Last updated: 2026-04-12

This is known as Pólya's Random Walk Theorem or Pólya's Recurrence Theorem, named after George Pólya who proved it in 1921.
Interestingly, Pólya came up with this theorem while walking through a park in Zurich, where he kept running into a couple multiple times. This led him to wonder about the probability of returning to the same spot in a random walk, ultimately leading to this profound mathematical discovery.
For each of the dd unit vectors eje_j:
P(Xi=ej)=P(Xi=−ej)=12d\begin{equation*}P(X_i = e_j) = P(X_i = -e_j) = \frac{1}{2d}\end{equation*}
Theorem (Pólya's Recurrence Theorem)
Simple random walk is recurrent in d≤2d \leq 2 and transient in d≥3d \geq 3.

Motivation

To steal a joke from Kakutani (U.C.L.A. colloquium talk): “A drunk man will eventually
find his way home but a drunk bird may get lost forever.”

Drunk man or two dimensional random walk

Random Walk in R2\mathbb{R}^2

Drunk bird three dimensional random walk

Random Walk in R3\mathbb{R}^3

Preliminary result

The foolowing theorem is Theorem 5.4.3 at [Durrett2019]

To analyze this case, we begin with a result that is valid for any random walk. Let τ0=0\tau_0 = 0 and τn=inf⁡{m>τn−1:Sm=0}\tau_n = \inf\{m > \tau_{n-1} : S_m = 0\} be the time of the nnth return to 0. From the strong Markov property, it follows that:
P(τn<∞)=P(τ1<∞)n\begin{equation*}P(\tau_n < \infty) = P(\tau_1 < \infty)^n\end{equation*}
Theorem
For any random walk, the following are equivalent:
  • P(τ1<∞)=1P(\tau_1 < \infty) = 1
  • P(Sm=0 i.o.)=1P(S_m = 0 \text{ i.o.}) = 1
  • ∑m=0∞P(Sm=0)=∞\sum_{m=0}^{\infty} P(S_m = 0) = \infty
\quad Proof. If P(τ1<∞)=1P(\tau_1 < \infty) = 1, then P(τn<∞)=1P(\tau_n < \infty) = 1 for all nn and P(Sm=0 i.o.)=1P(S_m = 0 \text{ i.o.}) = 1. Let
V=∑m=0∞1(Sm=0)=∑n=0∞1(τn<∞)\begin{equation*}V = \sum_{m=0}^{\infty} \mathbf{1}{(S_m=0)} = \sum_{n=0}^{\infty} \mathbf{1}{(\tau_n < \infty)}\end{equation*}
be the number of visits to 0, counting the visit at time 0. Taking expected value and using Fubini's theorem to put the expected value inside the sum:
EV=∑m=0∞P(Sm=0)=∑n=0∞P(τn<∞)=∑n=0∞P(τ1<∞)n=11−P(τ1<∞)□\begin{align*}EV &= \sum_{m=0}^{\infty} P(S_m = 0) = \sum_{n=0}^{\infty} P(\tau_n < \infty) \\&= \sum_{n=0}^{\infty} P(\tau_1 < \infty)^n = \frac{1}{1 - P(\tau_1 < \infty) } \quad \Box\end{align*}

Proof of Pólya's Recurrence Theorem

The foolowing theorem is Theorem 5.4.4 at [Durrett2019]

\quad Proof. Let ρd(m)=P(Sm=0)\rho_d(m) = P(S_m = 0). ρd(m)\rho_d(m) is 0 if mm is odd.

Simple random walk is recurrent in one dimension

From The De-Moivre Theorem, we get ::
ρ1(2n)∼(πn)−1/2 as n→∞\begin{equation*}\rho_1(2n) \sim (\pi n)^{-1/2} \text{ as } n \to \infty\end{equation*}
This fact and previous theorem give the result in one dimension.

Simple random walk is recurrent in two dimensions

Our next step is to show that the \emph{simple random walk is recurrent in two dimensions}. Note that in order for S2n=0S_{2n} = 0, we must for some 0≤m≤n0 \leq m \leq n have mm up steps, mm down steps, n−mn-m to the left, and n−mn-m to the right, so
ρ2(2n)=4−2n∑m=0n2n!m!m!(n−m)!(n−m)!\begin{equation*}\rho_2(2n) = 4^{-2n} \sum_{m=0}^n \frac{2n!}{m!m!(n-m)!(n-m)!}\end{equation*}=4−2n(2nn)∑m=0n(nm)(nn−m)=4−2n(2nn)2=ρ1(2n)2\begin{equation*}= 4^{-2n} \binom{2n}{n} \sum_{m=0}^n \binom{n}{m}\binom{n}{n-m} = 4^{-2n} \binom{2n}{n}^2 = \rho_1(2n)^2\end{equation*}
To see the next to last equality, consider choosing nn students from a class with nn boys and nn girls and observe that for some 0≤m≤n0 \leq m \leq n you must choose mm boys and n−mn-m girls. Using the asymptotic formula ρ1(2n)∼(πn)−1/2\rho_1(2n) \sim (\pi n)^{-1/2}, we get
ρ2(2n)∼(πn)−1\begin{equation*}\rho_2(2n) \sim (\pi n)^{-1}\end{equation*}
Since ∑n−1=∞\sum n^{-1} = \infty, the result follows from previous theorem.

Simple random walk is transient in three dimensions

Intuitively, this holds since the probability of being back at 0 after 2n2n steps is ∼cn−3/2\sim cn^{-3/2} and this is summable. We will not compute the probability exactly but will get an upper bound of the right order of magnitude. Again, since the number of steps in the directions ±ei\pm e_i must be equal for i=1,2,3i = 1,2,3:
ρ3(2n)=6−2n∑j,k(2n)!(j!k!(n−j−k)!)2\begin{equation*}\rho_3(2n) = 6^{-2n} \sum_{j,k} \frac{(2n)!}{(j!k!(n-j-k)!)^2}\end{equation*}=2−2n(2nn)(∑j,k3−nn!j!k!(n−j−k)!)2\begin{equation*}= 2^{-2n} \binom{2n}{n} \left(\sum_{j,k} 3^{-n} \frac{n!}{j!k!(n-j-k)!}\right)^2\end{equation*}≤2−2n(2nn)max⁡j,k3−nn!j!k!(n−j−k)!\begin{equation*}\leq 2^{-2n} \binom{2n}{n} \max_{j,k} 3^{-n} \frac{n!}{j!k!(n-j-k)!}\end{equation*}
where in the last inequality we have used the fact that if aj,ka_{j,k} are ≥0\geq 0 and sum to 1, then ∑j,kaj,k2≤max⁡j,kaj,k\sum_{j,k} a_{j,k}^2 \leq \max_{j,k} a_{j,k}. Our last step is to show
max⁡j,k3−nn!j!k!(n−j−k)!≤Cn−1\begin{equation*}\max_{j,k} 3^{-n} \frac{n!}{j!k!(n-j-k)!} \leq Cn^{-1}\end{equation*}
To do this, we note that:
  • If any of the numbers jj, kk, or n−j−kn-j-k is <[n/3]< [n/3] increasing the smallest number and decreasing the largest number decreases the denominator (since x(1−x)x(1-x) is maximized at 1/2), so the maximum occurs when all three numbers are as close as possible to n/3n/3
  • Stirling's formula implies
n!j!k!(n−j−k)!∼nnjjkk(n−j−k)n−j−knjk(n−j−k)⋅12π\begin{equation*}\frac{n!}{j!k!(n-j-k)!} \sim \frac{n^n}{j^jk^k(n-j-k)^{n-j-k}} \sqrt{\frac{n}{jk(n-j-k)}} \cdot \frac{1}{2\pi}\end{equation*}
Taking jj and kk within 1 of n/3n/3, the first term on the right is ≤C3n\leq C3^n, and the desired result follows.

Simple random walk is transient in dimensions greater than 3

Let Tn=(Sn1,Sn2,Sn3)T_n = (S_n^1, S_n^2, S_n^3), N(0)=0N(0) = 0 and N(n)=inf⁡m>N(n−1):Tm≠TN(n−1)N(n) = \inf{m > N(n-1) : T_m \neq T_{N(n-1)}}. It is easy to see that TN(n)T_{N(n)} is a three-dimensional simple random walk. Since TN(n)T_{N(n)} returns infinitely often to 0 with probability 0 and the first three coordinates are constant in between times N(n−1)N(n-1) and N(n)N(n), SnS_n is transient. □\Box

References