Pólya’s Theorem from the Green Function

Returns and the Green Function

For a random walk, recurrence asks whether the walk returns to where it started with probability one. The Green function answers a related quantitative question: how many visits to that state should we expect over the entire future? The connection is decisive. An infinite expected number of visits corresponds exactly to certain return, while a finite expected number corresponds to a positive chance of never returning.

Let \((\Omega,\mathcal{F},\mathbb{P})\) be a probability space, and let \((X_n)_{n\ge 0}\) be the simple symmetric nearest-neighbor walk on \(S=\mathbb{Z}^d\), for an integer \(d\ge 1\). At each step the walk independently adds one of the \(2d\) vectors \(\pm e_1,\ldots,\pm e_d\), each with probability \(1/(2d)\), where \(e_j\) is the \(j\)th coordinate unit vector. Thus every row of the transition kernel sums to \(2d\cdot(1/(2d))=1\). Write \(\mathbb{P}_0\) and \(\mathbb{E}_0\) for the walk started at the origin.

Because every step changes the parity of the sum of the coordinates, the walk can return to the origin only at even times. The Green function counts the initial visit at time zero as well as all later returns. The following criterion turns its finiteness into a recurrence classification.

Proof. Define \(u_n=\mathbb{P}_i(X_n=i)\), \(f_k=\mathbb{P}_i(T_i^+=k)\), \(U(z)=\sum_{n\ge0}u_nz^n\), and \(F(z)=\sum_{k\ge1}f_kz^k\), for \(0\le z<1\). For \(n\ge1\), partition the event \(\{X_n=i\}\) according to the time \(k\) of its first return. Conditional on \(T_i^+=k\), the Markov property says that the probability of being at \(i\) another \(n-k\) steps later is \(u_{n-k}\). Therefore \(u_n=\sum_{k=1}^n f_ku_{n-k}\). Since \(u_0=1\), multiplying by powers of \(z\) and summing gives \(U(z)=1+F(z)U(z)\). Both series converge for \(z<1\), because \(u_n\le1\) and \(f_k\le1\); also \(F(z)<1\). Hence \(U(z)=1/(1-F(z))\). As \(z\) increases to \(1\), the nonnegative series increase to \(G(i,i)\) and \(f=\sum_{k\ge1}f_k\), respectively. If \(f<1\), taking limits gives \(G(i,i)=1/(1-f)\). If \(f=1\), then \(F(z)\) increases to \(1\), so \(U(z)\) increases without bound and \(G(i,i)=\infty\). These are the only cases because \(f\) is a probability. \(\square\)

Fourier Form of the Green Function

For \(\theta=(\theta_1,\ldots,\theta_d)\in[-\pi,\pi]^d\), define the Fourier symbol \(\phi(\theta)=\frac1d\sum_{j=1}^d\cos\theta_j\). Fourier inversion for the lattice walk gives \(\mathbb{P}_0(X_n=0)=(2\pi)^{-d}\int_{[-\pi,\pi]^d}\phi(\theta)^n\,d\theta\). This is the return-probability Fourier formula established in the earlier material on Fourier inversion. In particular, it accounts for the zero probability of odd-time returns.

To sum the probabilities without assuming that a possibly singular expression can be integrated term by term at \(z=1\), first insert a factor \(r^n\) with \(0\le r<1\). The geometric series then converges uniformly in \(\theta\). The torus shift that adds \(\pi\) to every coordinate changes \(\phi\) to \(-\phi\) and preserves the integral. Averaging the two resulting expressions yields the Green-function formula.

Proof. For \(0\le r<1\), Fourier inversion and the uniformly convergent geometric series give \[ \sum_{n\ge0}r^n\mathbb{P}_0(X_n=0) =\frac{1}{(2\pi)^d}\int_{[-\pi,\pi]^d}\frac{d\theta}{1-r\phi(\theta)}. \] Under the torus shift \(\theta\mapsto\theta+(\pi,\ldots,\pi)\), the symbol changes sign. Thus the integral on the right is unchanged if its integrand is replaced by the average of \(1/(1-r\phi)\) and \(1/(1+r\phi)\). This average is \(1/(1-r^2\phi^2)\). As \(r\) increases to \(1\), this last integrand increases pointwise to \(1/(1-\phi^2)\), except at its singularities, where the limit is infinite. The left side increases to \(G(0,0)\), since its terms are nonnegative. The monotone convergence theorem therefore gives the asserted identity, including the possibility of an infinite integral. \(\square\)

The integrand can be singular only where \(\phi=1\) or \(\phi=-1\). Since each cosine lies between \(-1\) and \(1\), \(\phi=1\) requires every coordinate to be \(0\) modulo \(2\pi\), and \(\phi=-1\) requires every coordinate to be \(\pi\) modulo \(2\pi\). These are two points on the torus. Near the first point, writing \(|\theta|=(\sum_j\theta_j^2)^{1/2}\), the expansion \(1-\cos x=x^2/2+O(x^4)\) gives \(1-\phi(\theta)=|\theta|^2/(2d)+O(|\theta|^4)\) and \(1-\phi(\theta)^2=|\theta|^2/d+O(|\theta|^4)\). Near the second point, write \(\theta_j=\pi+y_j\) on the torus. Then \(\phi(\theta)=-\phi(y)\), so \(1-\phi(\theta)^2=1-\phi(y)^2\); the same quadratic behavior occurs there.

In particular, in a sufficiently small neighborhood of either singular point, \(1-\phi^2\) is bounded above and below by positive constants times the squared distance to that point. The Green integrand is therefore comparable to the inverse squared distance. Away from those neighborhoods its denominator is positive and continuous, so it is bounded. In \(d\) dimensions, polar coordinates reduce the local integrability question to \(\int_0^\varepsilon r^{d-3}\,dr\): this integral diverges for \(d=1,2\) and is finite for \(d\ge3\).

Worked Dimension Checks

Pólya’s Theorem

Proof. The Fourier Green-function formula expresses \(G(0,0)\) as the integral of \(1/(1-\phi^2)\) over the \(d\)-dimensional torus. Its only singularities are the points where \(\phi=1\) and \(\phi=-1\), and at each point the denominator is comparable to squared distance. In dimension \(d\), the local integral is therefore comparable to \(\int_0^\varepsilon r^{d-3}\,dr\). For \(d=1\) this is \(\int_0^\varepsilon r^{-2}\,dr=\infty\); for \(d=2\) it is \(\int_0^\varepsilon r^{-1}\,dr=\infty\); and for \(d\ge3\) it is finite because \(d-3\ge0\). The integral away from the two singularities is bounded. Hence \(G(0,0)\) is infinite in dimensions one and two and finite in dimensions at least three. By the Green-function criterion, these cases are respectively recurrent and transient. \(\square\)

The classification is unchanged if the walk starts at another lattice point: translation of every position by a fixed vector preserves the transition probabilities and identifies returns to that point with returns to the origin. A useful caution is that local integrability must use the volume element as well as the size of the integrand. In two dimensions, treating the integrand \(1/r^2\) as though the area element were just \(dr\), or as though it were \(r^2dr\), gives the wrong test. The correct area element is \(r\,dr\,d\alpha\), producing the divergent logarithmic integral \(\int_0^\varepsilon dr/r\).