From Return Probabilities to an Integral
For a random walk, the Green function at the starting point records the expected total number of visits back to that point. Fourier inversion expresses each return probability as an integral of a power of the walk’s Fourier symbol. The main issue is how to sum those integrals: the symbol can be negative, so its powers are not all nonnegative. For a simple symmetric walk, parity and a symmetry of the torus let us carry out the summation using nonnegative terms instead.
Fix an integer \(d\ge1\). On a probability space \((\Omega,\mathcal{F},\mathbb{P})\), let \(Y_1,Y_2,\ldots\) be independent, identically distributed random vectors, each taking the \(2d\) values \(e_1,-e_1,\ldots,e_d,-e_d\) with probability \(1/(2d)\). Here \(e_j\) is the \(j\)th coordinate vector in \(\mathbb{Z}^d\). Set \(X_0=0\) and \(X_n=\sum_{k=1}^nY_k\) for \(n\ge1\). This is a discrete-time Markov chain on the countable state space \(S=\mathbb{Z}^d\), with filtration \(\mathcal{F}_n=\sigma(Y_1,\ldots,Y_n)\) and \(\mathcal{F}_0=\{\varnothing,\Omega\}\). Its transition probabilities from any state to the \(2d\) neighboring states are \(1/(2d)\), and all other transition probabilities are zero; each row sums to \(2d\cdot(1/(2d))=1\).
Write \(\mathbb{T}^d=[-\pi,\pi]^d\), with opposite faces identified, and use normalized Lebesgue measure \(d\theta/(2\pi)^d\). The characteristic function of one step, called the Fourier symbol, is
In particular, \(\phi\) is real-valued and \(-1\le\phi(\theta)\le1\). The Fourier inversion formula for this walk is \(\mathbb{P}_0(X_n=0)=\int_{\mathbb{T}^d}\phi(\theta)^n\,d\theta/(2\pi)^d\). To see why, for an integer vector \(x\), the integral of \(e^{i\theta\cdot x}\) over \(\mathbb{T}^d\) is \(1\) if \(x=0\) and \(0\) otherwise. Thus this integral is the indicator of \(X_n=0\) when \(x=X_n\); taking expectations gives the formula. The exchange of expectation and integration is valid because the integrand has absolute value \(1\). Independence gives \(\mathbb{E}[e^{i\theta\cdot X_n}]=\phi(\theta)^n\).
The Integral Formula and Its Justification
Proof. Each step changes the sum of the coordinates by either \(1\) or \(-1\). Therefore, after an odd number of steps that sum cannot be zero, and \(X_n=0\) is impossible for odd \(n\). Consequently, \(G(0,0)=\sum_{m=0}^{\infty}\mathbb{P}_0(X_{2m}=0)\). By Fourier inversion, each term is \(\int_{\mathbb{T}^d}\phi(\theta)^{2m}\,d\theta/(2\pi)^d\). For every \(m\), the integrand \(\phi^{2m}\) is nonnegative, and the partial sums \(\sum_{m=0}^M\phi^{2m}\) increase pointwise as \(M\) increases. The monotone convergence theorem therefore gives $$ G(0,0)=\int_{\mathbb{T}^d}\left(\sum_{m=0}^{\infty}\phi(\theta)^{2m}\right)\frac{d\theta}{(2\pi)^d} =\int_{\mathbb{T}^d}\frac{1}{1-\phi(\theta)^2}\,\frac{d\theta}{(2\pi)^d}. $$ The geometric-series identity holds where \(|\phi|<1\), and where \(|\phi|=1\) the series and the displayed quotient are both \(+\infty\). For this symbol, \(\phi=1\) only when every coordinate is \(0\) modulo \(2\pi\), and \(\phi=-1\) only when every coordinate is \(\pi\) modulo \(2\pi\); these are measure-zero sets. Translation of the torus by \((\pi,\ldots,\pi)\) preserves normalized Lebesgue measure and sends \(\phi\) to \(-\phi\), since \(\cos(\theta_j+\pi)=-\cos\theta_j\). Hence the integrals of \(1/(1-\phi)\) and \(1/(1+\phi)\) are equal, with equality understood for extended nonnegative integrals. Away from the two measure-zero sets, $$ \frac12\left(\frac{1}{1-\phi}+\frac{1}{1+\phi}\right)=\frac{1}{1-\phi^2}. $$ Integrating this identity and using the equality of the two integrals yields \(\int 1/(1-\phi)=\int 1/(1-\phi^2)=G(0,0)\), as required. \(\square\)
The proof’s order matters. It first sums the even powers, which are nonnegative, and only then uses the torus symmetry to rewrite the result in the requested form. An equivalent regularization makes the limiting step explicit: for \(0\le r<1\), \(\sum_{m\ge0}r^{2m}\phi^{2m}=1/(1-r^2\phi^2)\). As \(r\) increases to \(1\), the summands and their partial sums increase, so monotone convergence gives the same extended integral limit. This procedure does not require the Green function to be finite.
Worked Example: The First Three Return Terms in One Dimension
Take \(d=1\). The walk is on \(S=\mathbb{Z}\), and from each \(i\) it moves to \(i-1\) and \(i+1\) with probability \(1/2\) each; the row sum is \(1/2+1/2=1\). Its symbol is \(\phi(\theta)=\cos\theta\). Compute the Green-function partial sum through time \(4\), both from paths and from the Fourier integrals.
At time \(0\), the walk is at the origin with probability \(1\). At times \(1\) and \(3\), it cannot return: an odd number of unit steps cannot sum to zero. At time \(2\), the two returning paths are \(+1,-1\) and \(-1,+1\), each with probability \(1/4\). Thus \(\mathbb{P}_0(X_2=0)=2(1/4)=1/2\).
At time \(4\), a returning path must have two \(+1\) steps and two \(-1\) steps. There are \(\binom{4}{2}=6\) such paths, each of probability \((1/2)^4=1/16\), so \(\mathbb{P}_0(X_4=0)=6/16=3/8\). The partial sum is \(1+1/2+3/8=15/8\).
Fourier inversion checks each nonzero return term: \(\int_{-\pi}^{\pi}\cos^2\theta\,d\theta/(2\pi)=1/2\), since \(\cos^2\theta=(1+\cos2\theta)/2\) and the integral of \(\cos2\theta\) is zero. Also \(\cos^4\theta=(3+4\cos2\theta+\cos4\theta)/8\), so its normalized integral is \(3/8\). The Fourier partial sum is therefore \(1+1/2+3/8=15/8\), matching the path count.
Worked Example: Four-Step Returns on the Square Lattice
For \(d=2\), the walk is on \(S=\mathbb{Z}^2\), and it moves to each of its four neighbors with probability \(1/4\); each transition row sums to \(4(1/4)=1\). The symbol is \(\phi(\theta_1,\theta_2)=(\cos\theta_1+\cos\theta_2)/2\). Compute the return probabilities at times \(2\) and \(4\).
A two-step return requires choosing one of the four first steps and then its opposite. There are \(4\cdot1=4\) such paths among \(4^2=16\) equally likely paths, giving \(1/4\). For four steps, a returning path either uses one coordinate axis for all four moves, or uses each axis twice. In the first case, there are \(2\binom{4}{2}=12\) paths: choose the axis in \(2\) ways and the two positions for its positive direction in \(\binom42=6\) ways. In the second case, choose the two positions for horizontal moves in \(\binom42=6\) ways, then choose the sign order on the horizontal and vertical moves in \(2\cdot2=4\) ways, giving \(24\) paths. There are \(12+24=36\) returning paths out of \(4^4=256\), so the probability is \(36/256=9/64\).
For a Fourier check, set \(c_j=\cos\theta_j\). The normalized integral of \(c_j^2\) is \(1/2\), and that of \(c_j^4\) is \(3/8\); integrals factor across coordinates. Thus $$ \int_{\mathbb{T}^2}\phi^2\,\frac{d\theta}{(2\pi)^2} =\frac14\left(\frac12+\frac12\right)=\frac14, $$ and $$ \int_{\mathbb{T}^2}\phi^4\,\frac{d\theta}{(2\pi)^2} =\frac1{16}\left(\frac38+6\cdot\frac14+\frac38\right) =\frac1{16}\cdot\frac94=\frac9{64}. $$ These agree with the path counts. The Green-function partial sum through time \(4\) is \(1+1/4+9/64=89/64\).
Worked Example: Why the Signed Geometric Series Needs Care
In dimension \(1\), evaluate the symbol at \(\theta=2\pi/3\). Since \(\cos(2\pi/3)=-1/2\), the pointwise series in powers of \(\phi\) is \(1-1/2+1/4-\cdots\), whose sum is \(1/(1+1/2)=2/3\). Its even-power series instead sums to \(1/(1-1/4)=4/3\). The two pointwise sums are not equal.
The formula in the theorem is not obtained by asserting that \(\sum_{n\ge0}\phi^n\) equals \(\sum_{m\ge0}\phi^{2m}\) pointwise. At the translated point \(\theta+\pi=5\pi/3\), \(\cos(5\pi/3)=1/2\), so the two symbol values are opposites. Averaging the two values of \(1/(1-\phi)\) gives \(\tfrac12(2+2/3)=4/3\), which equals \(1/(1-\phi^2)\) at either point. This calculation illustrates the symmetry step in the proof; it does not replace integration over the torus.
What the Formula Does—and Does Not—Say
The integral representation converts an infinite sum of return probabilities into one integral determined by the Fourier symbol. The equality is valid even when both sides are infinite. Establishing whether the integral is finite requires analyzing the symbol near points where \(\phi=1\); the formula itself does not make that local-integrability analysis.
Common mistake. One might write \(\sum_{n\ge0}\int\phi^n=\int\sum_{n\ge0}\phi^n=\int1/(1-\phi)\) because the finite geometric-series identity is familiar. This skips a necessary justification: \(\phi^n\) can be negative, so the integrands are not a nonnegative increasing sequence. The correction is to use the impossible odd-time returns and write \(G(0,0)=\sum_{m\ge0}\int\phi^{2m}\). These integrands are nonnegative, so monotone convergence justifies the exchange and yields \(\int1/(1-\phi^2)\). Only after that step does torus symmetry give the integral of \(1/(1-\phi)\).
Check Your Understanding
Use the definitions and the order of justification from the theorem when answering.
- Why is \(\mathbb{P}_0(X_n=0)=0\) for odd \(n\) for this walk?
- For \(d=1\), count the returning paths at time \(6\) and compute \(\mathbb{P}_0(X_6=0)\).
- State precisely which sequence of integrands is nonnegative and increasing in the proof.
- Under translation by \((\pi,\ldots,\pi)\), what happens to \(\phi\), and why is normalized torus measure unchanged?
- Does the integral formula alone imply that \(G(0,0)\) is finite? Explain what the formula says if the integral diverges.