Skip to content

Pólya's Recurrence Theorem

Random Walk in R2\mathbb{R}^2
PÓLYA'S RECURRENCE THEOREM
The simple symmetric random walk on Zd\mathbb{Z}^d is recurrent in d≤2d \leq 2 and transient in d≥3d \geq 3.
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.
Pólya [Po21] discovered that a simple symmetric random walk on Zd\mathbb{Z}^d is recurrent for d≤2d \leq 2 and transient otherwise.
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.
Random Walk in R3\mathbb{R}^3
Let
S0=0,Sn=X1+⋯+Xn,\begin{equation*}S_0=0, \qquad S_n=X_1+\cdots+X_n,\end{equation*}
where the increments XiX_i take values in Zd\mathbb{Z}^d. For each of the dd unit vectors eje_j:
P(Xi=ej)=P(Xi=−ej)=12d\begin{equation*}\mathbb{P}(X_i = e_j) = \mathbb{P}(X_i = -e_j) = \frac{1}{2d}\end{equation*}
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.”

The foolowing theorem is Theorem 5.4.3 at [Durrett2019]

We begin with a result that is valid for any random walk. Let
τ0=0,τn:=inf⁡{m>τn−1:Sm=0},n≥1,\begin{equation*}\tau_0=0,\qquad \tau_n:=\inf\{m>\tau_{n-1}:S_m=0\}, \quad n\ge 1,\end{equation*}
so that τn\tau_n is the time of the nnth return to the origin. The key point is that after each return to 00, the walk starts again from the same position and has the same future law as at time 00. Therefore, by the strong Markov property,
P(τn<∞)=P(τ1<∞)n\begin{equation*}\mathbb{P}(\tau_n < \infty) = \mathbb{P}(\tau_1 < \infty)^n\end{equation*}
LEMMA
For any random walk, the following are equivalent:
  • P(τ1<∞)=1\mathbb{P}(\tau_1 < \infty) = 1
  • P(Sm=0 i.o.)=1\mathbb{P}(S_m = 0 \text{ i.o.}) = 1
  • ∑m=0∞P(Sm=0)=∞\sum_{m=0}^{\infty} \mathbb{P}(S_m = 0) = \infty
In words, the walk is recurrent exactly when it returns to 0 infinitely often, and this is equivalent to the divergence of the sum of the return probabilities.
\quad Proof. Statement 1 implies 2: if P(τ1<∞)=1\mathbb{P}(\tau_1 < \infty) = 1, then after each return to 0 the walk starts again from 0, so the strong Markov property gives P(τn<∞)=1\mathbb{P}(\tau_n < \infty) = 1 for all nn. Hence the walk returns to 0 infinitely often almost surely, that is, P(Sm=0 i.o.)=1\mathbb{P}(S_m = 0 \text{ i.o.}) = 1.
To compare 1 and 3, 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.\begin{equation*}\mathbb{E}V = \sum_{m=0}^{\infty} \mathbb{P}(S_m = 0) = \sum_{n=0}^{\infty} \mathbb{P}(\tau_n < \infty) = \sum_{n=0}^{\infty} \mathbb{P}(\tau_1 < \infty)^n.\end{equation*}
If P(τ1<∞)<1\mathbb{P}(\tau_1 < \infty) < 1, then this is a convergent geometric series, so
EV=11−P(τ1<∞)<∞,\begin{equation*}\mathbb{E}V = \frac{1}{1 - \mathbb{P}(\tau_1 < \infty)} < \infty,\end{equation*}
and therefore 3 is false. If P(τ1<∞)=1\mathbb{P}(\tau_1 < \infty) = 1, then every term in the last sum equals 1, so EV=∞\mathbb{E}V = \infty, which means that 3 holds. Thus 1 and 3 are equivalent. Also, 2 implies 3 because if Sm=0S_m = 0 infinitely often almost surely, then V=∞V = \infty almost surely, hence EV=∞\mathbb{E}V = \infty. Together with 1 implies 2, this proves the lemma. □\Box

The foolowing theorem is Theorem 5.4.4 at [Durrett2019]

\quad Proof. To study recurrence, it is natural to track the return probabilities
ρd(m):=P(Sm=0).\begin{equation*}\rho_d(m):=\mathbb{P}(S_m=0).\end{equation*}
These tell us how likely the walk is to be at the origin at time mm. In particular, ρd(m)=0\rho_d(m)=0 for odd mm, because the walk cannot return to the origin in an odd number of steps.
ρ1(2n)=P(S2n=0)=(2nn)2−2n=(2n)!(n!)22−2n.\begin{equation*}\rho_1(2n)=\mathbb{P}(S_{2n}=0)=\binom{2n}{n}2^{-2n}=\frac{(2n)!}{(n!)^2}2^{-2n}.\end{equation*}
By Stirling's formula; for a detailed proof of this asymptotic, see the De Moivre-Laplace theorem,
(2nn)2−2n∼(πn)−1/2⟹ρ1(2n)∼(πn)−1/2.\begin{equation*}\binom{2n}{n}2^{-2n}\sim (\pi n)^{-1/2} \quad \Longrightarrow \quad \rho_1(2n)\sim (\pi n)^{-1/2}.\end{equation*}
Since
∑n=1∞n−1/2=∞⟹∑m=0∞ρ1(m)=∞.\begin{equation*}\sum_{n=1}^\infty n^{-1/2}=\infty \quad \Longrightarrow \quad \sum_{m=0}^\infty \rho_1(m)=\infty.\end{equation*}
Therefore, by the previous theorem, the one-dimensional simple random walk is recurrent.
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)!=4−2n(2nn)∑m=0n(nm)(nn−m)=4−2n(2nn)2=ρ1(2n)2\begin{equation*}\rho_2(2n) = 4^{-2n} \sum_{m=0}^n \frac{2n!}{m!m!(n-m)!(n-m)!} = 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.
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=2−2n(2nn)(∑j,k3−nn!j!k!(n−j−k)!)2≤2−2n(2nn)max⁡j,k3−nn!j!k!(n−j−k)!\begin{equation*}\rho_3(2n) = 6^{-2n} \sum_{j,k} \frac{(2n)!}{(j!k!(n-j-k)!)^2}= 2^{-2n} \binom{2n}{n} \left(\sum_{j,k} 3^{-n} \frac{n!}{j!k!(n-j-k)!}\right)^2 \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.
We reduce the problem to the three-dimensional case by looking only at the first three coordinates. Let
Tn:=(Sn1,Sn2,Sn3).\begin{equation*}T_n := (S_n^1,S_n^2,S_n^3).\end{equation*}
This process changes only when the original walk takes a step in one of the directions ±e1,±e2,±e3\pm e_1,\pm e_2,\pm e_3. Define the successive times of such changes by
N(0)=0,N(n):=inf⁡{m>N(n−1):Tm≠TN(n−1)},n≥1.\begin{equation*}N(0)=0,\qquad N(n):=\inf\{m>N(n-1):T_m\neq T_{N(n-1)}\}, \qquad n\geq 1.\end{equation*}
Between the times N(n−1)N(n-1) and N(n)N(n), the first three coordinates do not move, so TmT_m is constant on each interval [N(n−1),N(n))[N(n-1),N(n)).
Now consider the embedded process
Yn:=TN(n).\begin{equation*}Y_n:=T_{N(n)}.\end{equation*}
At each time N(n)N(n), the original walk has just taken a step in one of the six directions ±e1,±e2,±e3\pm e_1,\pm e_2,\pm e_3, and by symmetry each of these six possibilities has probability 1/61/6. Therefore (Yn)(Y_n) is a three-dimensional simple symmetric random walk.
We already proved that the three-dimensional simple random walk is transient, so
P(Yn=0 i.o.)=0.\begin{equation*}\mathbb{P}(Y_n=0 \text{ i.o.})=0.\end{equation*}
If the original walk (Sn)(S_n) returned to 00 infinitely often, then at each such time the first three coordinates would also be equal to 00, so Tn=0T_n=0. Since TnT_n is constant between successive times N(n−1)N(n-1) and N(n)N(n), every such return of TnT_n to 00 would force Yk=0Y_k=0 for some kk. Thus infinitely many returns of (Sn)(S_n) to 00 would imply infinitely many returns of (Yn)(Y_n) to 00, which is impossible. Hence the simple random walk on Zd\mathbb{Z}^d is transient for every d>3d>3. □\Box

References