From a Fourier Integral to a Return-Probability Asymptotic
For a random walk, the probability of being back at the origin after many steps is a global quantity: it sums the probabilities of all paths that return. Fourier analysis turns that sum into an integral of a power of one function, the walk’s Fourier symbol. At large times, most of the integral becomes negligible. The leading contribution comes from small neighborhoods of the points where the symbol has absolute value one. For the simple symmetric walk on \(\mathbb{Z}^d\), there are two such points, and both matter.
Fix an integer \(d\ge 1\). On a probability space \((\Omega,\mathcal{F},\mathbb{P})\), let \((X_n)_{n\ge0}\) be the simple symmetric random walk on the state space \(S=\mathbb{Z}^d\), with discrete time \(n\). Start at \(X_0=0\). At each step, independently of the past, the walk moves by \(+e_j\) or \(-e_j\), each with probability \(1/(2d)\), for one of the coordinate unit vectors \(e_1,\ldots,e_d\). Write \(p_n=\mathbb{P}(X_n=0)\).
The Fourier symbol of one step is the characteristic function of the increment: \(\phi(\theta)=\frac{1}{d}\sum_{j=1}^d\cos\theta_j\), for \(\theta\) on the \(d\)-dimensional torus \([-\pi,\pi]^d\) with opposite faces identified. Fourier inversion for lattice return probabilities gives \(p_n=(2\pi)^{-d}\int_{[-\pi,\pi]^d}\phi(\theta)^n\,d\theta\). The aim here is to analyze this integral as \(n\) grows, not to derive Fourier inversion itself.
Why There Are Two Relevant Points
Each step changes the parity of the sum of the coordinates of \(X_n\). Since this sum is even at the origin, the walk cannot return after an odd number of steps. This proves \(p_{2n+1}=0\), including \(p_1=0\). At every even time a return is possible: repeating the pair of steps \(+e_1,-e_1\) gives a returning path. Thus “even-time restriction” does not mean that every even-time return probability is zero.
The same parity structure appears in the Fourier integral. Since \(-1\le\phi(\theta)\le1\), the integrand \(\phi(\theta)^{2n}\) can be large only near points where \(|\phi(\theta)|=1\). An average of numbers in \([-1,1]\) has absolute value one only when all the numbers being averaged equal \(1\), or all equal \(-1\). Therefore \(|\phi(\theta)|=1\) precisely at the two torus points \(0=(0,\ldots,0)\) and \(\boldsymbol{\pi}=(\pi,\ldots,\pi)\). At the first, \(\phi=1\); at the second, \(\phi=-1\). Because the exponent \(2n\) is even, both points contribute positively.
Local Gaussian Approximation
Near \(0\), Taylor expansion of cosine gives \(\cos u=1-u^2/2+O(u^4)\) as \(u\to0\). Consequently, \(\phi(\theta)=1-|\theta|^2/(2d)+O(|\theta|^4)\), where \(|\theta|^2=\sum_{j=1}^d\theta_j^2\). For a fixed vector \(y\), set \(\theta=y/\sqrt{n}\). The expansion then gives \(\phi(y/\sqrt{n})=1-|y|^2/(2dn)+O(|y|^4/n^2)\), and hence \(\phi(y/\sqrt{n})^{2n}\to \exp(-|y|^2/d)\). The factor \(2n\) in the exponent is important: the quadratic term is \(-n|\theta|^2/d\), not \(-n|\theta|^2/(2d)\).
To pass from this pointwise approximation to an integral asymptotic, the contribution away from the two maxima must also be controlled. The following proof supplies that control and the needed domination.
Proof. The parity argument above proves the assertion for odd times. For even times, choose disjoint fixed neighborhoods \(U_0\) and \(U_{\boldsymbol{\pi}}\) of the two torus points. On the closed complement of these neighborhoods, continuity of \(\phi\) and the characterization of its absolute-value-one points imply \(|\phi(\theta)|\le\rho\) for some \(\rho<1\). The absolute value of the integral over that complement is at most \((2\pi)^d\rho^{2n}\). After multiplication by \(n^{d/2}\), this bound tends to zero: its logarithm, apart from a constant, is \((d/2)\log n+2n\log\rho\), which tends to \(-\infty\) because \(\log\rho<0\).
It remains to evaluate the contribution near \(0\). Choose \(U_0\) small enough that \(\phi\) is positive there. The function \((1-\cos u)/u^2\), extended at \(u=0\) by its limit \(1/2\), is continuous and positive on a sufficiently small closed interval. It therefore has a positive lower bound \(c_0\) there. It follows that, for \(\theta\in U_0\), \(1-\phi(\theta)=d^{-1}\sum_j(1-\cos\theta_j)\ge(c_0/d)|\theta|^2\). Using \(1-v\le e^{-v}\) for \(v\ge0\), we obtain \(0\le\phi(\theta)^{2n}\le\exp(-2c_0n|\theta|^2/d)\). Rescale by \(y=\sqrt{n}\theta\). The rescaled integrand, set equal to zero outside \(\sqrt{n}U_0\), is bounded by \(\exp(-2c_0|y|^2/d)\), an integrable function on \(\mathbb{R}^d\). For each fixed \(y\), the Taylor expansion above shows that it tends to \(\exp(-|y|^2/d)\). The dominated convergence theorem therefore gives \(\lim_{n\to\infty}n^{d/2}\int_{U_0}\phi(\theta)^{2n}\,d\theta=\int_{\mathbb{R}^d}e^{-|y|^2/d}\,dy=(\pi d)^{d/2}\). The last equality is the standard Gaussian integral, obtained by multiplying the one-dimensional Gaussian integral in each coordinate.
In coordinates \(u\) centered at \(\boldsymbol{\pi}\) on the torus, \(\phi(\boldsymbol{\pi}+u)=-\phi(u)\), since \(\cos(\pi+u_j)=-\cos u_j\) for every coordinate. Thus \(\phi(\boldsymbol{\pi}+u)^{2n}=\phi(u)^{2n}\), and the neighborhood of \(\boldsymbol{\pi}\) contributes the same integral as the neighborhood of \(0\). Including the Fourier normalization and the negligible complement gives \((2\pi)^{-d}\,2\,(\pi d)^{d/2}n^{-d/2}\). Simplifying this expression gives \(2(d/(4\pi n))^{d/2}\). Its leading constant is positive, so the additive error that is negligible after multiplication by \(n^{d/2}\) also gives the stated ratio asymptotic. Substituting \(n=m/2\) gives the equivalent even-time form. \(\square\)
Worked Asymptotics in Three Dimensions
Worked Example: The Two-Dimensional Walk
Find the leading return-probability asymptotic for the simple symmetric walk on \(\mathbb{Z}^2\), and identify how much comes from each Fourier maximum.
Here \(\phi(\theta_1,\theta_2)=(\cos\theta_1+\cos\theta_2)/2\), and its expansion at the origin is \(\phi(\theta)=1-(\theta_1^2+\theta_2^2)/4+O(|\theta|^4)\). At time \(2n\), scaling \(\theta=y/\sqrt n\) gives the limiting integrand \(\exp(-|y|^2/2)\). Its integral over \(\mathbb{R}^2\) is \((2\pi)^{2/2}=2\pi\). The Fourier normalization is \((2\pi)^{-2}=1/(4\pi^2)\), so the contribution from the origin is \((1/(4\pi^2))(2\pi)n^{-1}=1/(2\pi n)\).
The point \((\pi,\pi)\) has symbol value \(-1\) and gives the same contribution at even times. Adding the two contributions gives \(1/(\pi n)\).
Check: The general formula with \(d=2\) gives \(2(2/(4\pi n))^1=2/(2\pi n)=1/(\pi n)\), agreeing with the local calculation. At odd times the return probability is zero by parity, so the asymptotic is only along even times.
Worked Example: The Three-Dimensional Walk
Compute the leading constant for the walk on \(\mathbb{Z}^3\), first at each maximum and then in total.
The symbol is \(\phi(\theta)=\frac13(\cos\theta_1+\cos\theta_2+\cos\theta_3)\). Its expansion at \(0\) is \(\phi(\theta)=1-|\theta|^2/6+O(|\theta|^4)\). At time \(2n\), the rescaled limiting integrand is \(e^{-|y|^2/3}\), whose integral over \(\mathbb{R}^3\) is \((3\pi)^{3/2}=3\sqrt{3}\,\pi^{3/2}\). The normalization is \((2\pi)^{-3}=1/(8\pi^3)\). Thus the origin contributes \((3\sqrt{3}\,\pi^{3/2})/(8\pi^3)n^{-3/2}=3\sqrt{3}/(8\pi^{3/2})\,n^{-3/2}\).
The other maximum contributes this same amount. The total leading term is therefore \(3\sqrt{3}/(4\pi^{3/2})\,n^{-3/2}\).
Check: Substituting \(d=3\) into the theorem gives \(2(3/(4\pi n))^{3/2}=2(3\sqrt{3})/(8\pi^{3/2}n^{3/2})=3\sqrt{3}/(4\pi^{3/2})\,n^{-3/2}\), exactly the sum of the two local contributions.
Worked Example: Converting the Four-Dimensional Formula to Time \(m\)
For the walk on \(\mathbb{Z}^4\), express the leading asymptotic using the actual time \(m\), and check the conversion from the number of two-step pairs.
At time \(2n\), the theorem gives \(p_{2n}\sim2(4/(4\pi n))^{4/2}=2(1/(\pi n))^2=2/(\pi^2n^2)\). Since the actual time is \(m=2n\), we have \(n=m/2\). Substitution gives \(2/(\pi^2(m/2)^2)=2(4/(\pi^2m^2))=8/(\pi^2m^2)\).
Check: The even-time form of the theorem, evaluated directly at \(d=4\), is \(2(4/(2\pi m))^{4/2}=2(2/(\pi m))^2=8/(\pi^2m^2)\). The direct substitution and the general even-time expression agree. No corresponding positive asymptotic applies at odd \(m\), because \(p_m=0\) there.
Common Pitfall: Counting Only One Maximum
A tempting but incorrect calculation is to expand \(\phi\) near \(0\), evaluate that Gaussian contribution, and treat it as the whole return probability. For the two-dimensional walk, this gives \(1/(2\pi n)\) at time \(2n\), as computed above. That is only the contribution from one point. The second point, \((\pi,\pi)\), has \(\phi=-1\), but its contribution is positive because the exponent is even. The corrected leading term is twice the one-maximum value, \(1/(\pi n)\).
This distinction is not a small error in the approximation: it changes the leading constant by a factor of two. The integral at odd times behaves differently because the two maxima have opposite signs before taking the power. In this walk, the parity argument gives the exact answer \(p_{2n+1}=0\), so one should not apply the even-time Gaussian asymptotic to odd times.
The method illustrates a general feature of Fourier asymptotics: the local expansion determines the shape and scale of the contribution near each maximum, while the global identification of every maximum determines the total constant. For this walk, quadratic decay around either maximum gives order \(n^{-d/2}\), and the two equal contributions yield the factor \(2\). The calculation concerns the return probability itself; conclusions about sums over time require an additional argument.
Check Your Understanding
Use the Fourier symbol and the two-maximum calculation to answer the following.
- Why is \(p_{2n+1}=0\) for the walk on \(\mathbb{Z}^d\)? Give a path showing that a return is possible at every even time.
- For \(d=1\), use the theorem to compute the leading asymptotic of \(p_{2n}\). How does the coefficient change if only the maximum at \(0\) is counted?
- Explain why \(\phi(\boldsymbol{\pi}+u)^{2n}=\phi(u)^{2n}\) for \(u\) near \(0\).
- In dimension \(d=4\), what is the leading asymptotic when written in terms of the even time \(m\), rather than \(n=m/2\)?
- In the proof, what ensures that the part of the Fourier integral outside the two neighborhoods does not affect the leading term?