Tutorials › Probability Theory (Graduate) › Green-Function Asymptotics for Transient Lattice Walks

Home  /  Tutorials  /  Random Walks and Potential Theory

Random Walks and Potential Theory · Tutorial 934 of 946

Green-Function Asymptotics for Transient Lattice Walks

Use Fourier inversion to obtain the Green function’s precise power-law decay, then translate that decay into asymptotics for lattice hitting probabilities.

Advanced 13 min read

What You'll Learn

  • Define the Green function of simple random walk on \(\mathbb{Z}^d\) and obtain its Fourier representation.
  • Identify the singularity of the Fourier integrand that determines large-distance behavior.
  • Derive the leading constant and power-law decay for dimensions \(d\ge3\).
  • Relate expected visit counts to the probability of ever hitting a site.
  • Apply the asymptotic and exact identities to examples in dimensions three and four.

Why the Green Function Has a Spatial Decay

For simple random walk in dimensions \(d\ge3\), a distant site is less likely to be visited than a nearby one. The Green function quantifies this difference by counting the expected number of visits. Fourier inversion turns that count into an integral, and the integral’s singularity near zero determines how rapidly the count decays with distance.

Here the walk starts at the origin and at each step chooses each of the \(2d\) nearest neighbors with probability \(1/(2d)\). Write \(S_n\) for its position at time \(n\), and let \(|x|\) denote the Euclidean norm of \(x\in\mathbb{Z}^d\). Transience in dimensions \(d\ge3\), as given by the Fourier recurrence criterion, ensures that the expected number of visits to any fixed site is finite.

Definition: The Green function of simple random walk is $$ G(x)=\sum_{n=0}^{\infty}\mathbb{P}_0(S_n=x), \qquad x\in\mathbb{Z}^d. $$ It is the expected total number of visits to \(x\) by a walk started at the origin, counting a visit at time zero when \(x=0\).

The walk is periodic: it can return to a site only at times of the appropriate parity. The Green function nevertheless sums over all times, and its Fourier representation below remains valid. The relevant singularity is at frequency zero, where the one-step characteristic function approaches one.

The Fourier Representation

For \(\theta=(\theta_1,\ldots,\theta_d)\in[-\pi,\pi]^d\), the characteristic function of one step is

$$ \phi(\theta)=\frac{1}{d}\sum_{j=1}^d \cos(\theta_j). $$

Indeed, coordinate \(j\) is chosen with total probability \(1/d\), and the two possible signs contribute \((e^{i\theta_j}+e^{-i\theta_j})/(2d)=\cos(\theta_j)/d\). Fourier inversion for the \(n\)-step distribution gives

$$ \mathbb{P}_0(S_n=x) = \frac{1}{(2\pi)^d}\int_{[-\pi,\pi]^d} e^{-i\theta\cdot x}\phi(\theta)^n\,d\theta. $$

To sum over \(n\), first insert a factor \(r^n\), where \(0<r<1\). The resulting geometric series gives an integrand \(1/(1-r\phi(\theta))\). Letting \(r\) increase to one yields the Green function formula.

Theorem: For \(d\ge3\) and \(x\in\mathbb{Z}^d\), $$ G(x)=\frac{1}{(2\pi)^d}\int_{[-\pi,\pi]^d} \frac{e^{-i\theta\cdot x}}{1-\phi(\theta)}\,d\theta. $$ The integral is finite; the value at the single singular point \(\theta=0\) is immaterial.

To justify the limit, near the origin \(1-\phi(\theta)\) is comparable to \(|\theta|^2\). For \(r\ge1/2\), the denominator \(1-r\phi(\theta)=(1-r)+r(1-\phi(\theta))\) is bounded below by a positive constant times \(|\theta|^2\) in a small neighborhood of zero. Away from zero, it stays bounded away from zero. Since \(|\theta|^{-2}\) is integrable in \(d\ge3\), dominated convergence applies to the integrals. On the probability side, the sums \(\sum_n r^n\mathbb{P}_0(S_n=x)\) increase to \(G(x)\). This proves the formula.

The Large-Distance Asymptotic

The Taylor expansion of cosine at zero gives

$$ 1-\phi(\theta) = \frac{|\theta|^2}{2d}+O(|\theta|^4), \qquad \theta\longrightarrow 0. $$

Thus the Fourier integrand has leading singular part \(2d/|\theta|^2\). The inverse Fourier transform of \(|\theta|^{-2}\) in \(\mathbb{R}^d\) is a constant times \(|x|^{2-d}\). A smooth cutoff can isolate the singularity at zero; the remaining smooth part decays faster, while the bounded-order correction to the singularity contributes a smaller term.

Theorem: For simple random walk on \(\mathbb{Z}^d\), \(d\ge3\), $$ G(x)\sim \frac{d\,\Gamma(d/2-1)}{2\pi^{d/2}}\,|x|^{2-d} \qquad\text{as }|x|\longrightarrow\infty. $$ Here \(\Gamma\) is the gamma function, and the asymptotic holds along lattice sites in any direction.

Proof. Regard the Fourier integrand as a periodic function on the \(d\)-dimensional torus. It is smooth except at the origin. Choose a smooth cutoff \(\chi\) supported near zero and equal to one on a smaller neighborhood. The Taylor expansion and its differentiated versions show that, near zero,

$$ \frac{1}{1-\phi(\theta)} = \frac{2d}{|\theta|^2}+h(\theta), \qquad |\partial^\alpha h(\theta)|\le C_\alpha|\theta|^{-|\alpha|}. $$

The cutoff contribution from \(h\) has Fourier coefficients \(O(|x|^{-d})\). To see the scale of this bound, decompose a neighborhood of zero into annuli of radius \(\rho\). An annulus of radius \(\rho\) has volume of order \(\rho^d\). When \(\rho\le |x|^{-1}\), boundedness of \(h\) makes its contribution at most a constant times \(\rho^d\); summing these annuli gives \(O(|x|^{-d})\). For \(\rho>|x|^{-1}\), integrate by parts \(N>d\) times in a coordinate direction for which \(|x_j|\ge |x|/\sqrt d\). The derivative bounds give an annular contribution bounded by a constant times \(\rho^d(|x|\rho)^{-N}\); summing again gives \(O(|x|^{-d})\). The part of the integrand away from zero is smooth and periodic, so repeated integration by parts makes its Fourier coefficients decay faster than any fixed inverse power of \(|x|\).

It remains to calculate the leading contribution from \(2d\chi(\theta)|\theta|^{-2}\). The cutoff does not change its leading large-\(|x|\) behavior: the difference from the full-space inverse transform is smooth away from zero and contributes a lower-order term. The full-space transform can be computed from

$$ \frac{1}{|\theta|^2}=\int_0^\infty e^{-t|\theta|^2}\,dt. $$

The inverse Fourier transform of the Gaussian \(e^{-t|\theta|^2}\), with the convention \((2\pi)^{-d}\int e^{-i\theta\cdot x}(\cdot)\,d\theta\), is \((4\pi t)^{-d/2}e^{-|x|^2/(4t)}\). Integrating in \(t\) and substituting \(u=|x|^2/(4t)\) gives

$$ \frac{1}{(2\pi)^d}\int_{\mathbb{R}^d} \frac{e^{-i\theta\cdot x}}{|\theta|^2}\,d\theta = \int_0^\infty (4\pi t)^{-d/2}e^{-|x|^2/(4t)}\,dt = \frac{\Gamma(d/2-1)}{4\pi^{d/2}}|x|^{2-d}. $$

Multiplication by \(2d\) therefore gives the claimed leading term. The \(O(|x|^{-d})\) correction is smaller than \(|x|^{2-d}\) by a factor of order \(|x|^{-2}\). This proves the asymptotic, including its constant. \(\square\)

Worked Example: The Leading Constants in Dimensions Three and Four

Worked Example: The Leading Constants in Dimensions Three and Four

For \(d=3\), the theorem gives the coefficient

$$ \frac{3\Gamma(1/2)}{2\pi^{3/2}} = \frac{3\sqrt{\pi}}{2\pi^{3/2}} = \frac{3}{2\pi}. $$

Consequently, for lattice sites \(x\in\mathbb{Z}^3\) tending to infinity,

$$ G(x)\sim\frac{3}{2\pi|x|}. $$

For \(d=4\), \(\Gamma(4/2-1)=\Gamma(1)=1\), so

$$ G(x)\sim\frac{4}{2\pi^2}|x|^{-2} =\frac{2}{\pi^2|x|^2}. $$

Both dimensions have transient walks, but the decay differs: the expected number of visits at distance \(R\) is of order \(R^{-1}\) in three dimensions and \(R^{-2}\) in four.

From Visit Counts to Hitting Probabilities

The Green function measures expected visits, whereas a hitting probability asks whether the walk ever reaches a site. For a single target, the two quantities are directly related. Define \(T_x=\inf\{n\ge0:S_n=x\}\), with \(T_x=\infty\) if the set is empty.

Theorem: If \(x\ne0\), then $$ \mathbb{P}_0(T_x<\infty)=\frac{G(x)}{G(0)}. $$ More generally, for a walk started at \(y\ne x\), translation invariance gives $$ \mathbb{P}_y(T_x<\infty)=\frac{G(x-y)}{G(0)}. $$

Proof. Before time \(T_x\), there are no visits to \(x\). On the event \(T_x<\infty\), the walk is at \(x\) at time \(T_x\). By the strong Markov property, its expected number of visits to \(x\) from that time onward, including the visit at \(T_x\), is \(G(0)\): after translation, this is the expected number of visits to the starting site. Therefore

$$ G(x)=\mathbb{P}_0(T_x<\infty)G(0). $$

Since \(G(0)\ge1\), division gives the first identity. Starting from \(y\), translate the walk by \(-y\); the target becomes \(x-y\), which gives the second identity. \(\square\)

Combining this identity with the asymptotic theorem gives a precise hitting-probability estimate:

$$ \mathbb{P}_0(T_x<\infty) \sim \frac{d\,\Gamma(d/2-1)}{2\pi^{d/2}G(0)} \,|x|^{2-d}. $$

The constant \(G(0)\) is the expected total number of visits to the starting site. The decay exponent is the same as for \(G(x)\); normalizing by \(G(0)\) converts visit counts into the probability of ever reaching the target.

Worked Example: Hitting a Distant Site in Three Dimensions

Worked Example: Hitting a Distant Site in Three Dimensions

Let \(x\in\mathbb{Z}^3\) be a target whose distance from the origin tends to infinity. The three-dimensional asymptotic and the hitting identity give

$$ \mathbb{P}_0(T_x<\infty) = \frac{G(x)}{G(0)} \sim \frac{3}{2\pi G(0)}\,\frac{1}{|x|}. $$

For instance, if \(x=(R,0,0)\) with positive integer \(R\), then \(|x|=R\), and the probability is asymptotic to \(3/(2\pi G(0)R)\). This is an asymptotic estimate, not an exact formula for finite \(R\). In particular, the walk has positive probability of never hitting the target, and that probability approaches one as \(R\) grows.

Worked Example: An Exact Neighbor Hitting Probability

Worked Example: An Exact Neighbor Hitting Probability

Let \(e_1=(1,0,\ldots,0)\). Translation invariance and coordinate-permutation and sign symmetries imply that all \(2d\) neighbors of the origin have the same Green function value. Decompose visits to the origin into the initial visit and visits after the first step. This gives

$$ G(0) = 1+\frac{1}{2d}\sum_{|e|=1}G(-e) = 1+\frac{1}{2d}(2d)G(e_1) = 1+G(e_1). $$

The hitting identity now yields the exact probability

$$ \mathbb{P}_0(T_{e_1}<\infty) = \frac{G(e_1)}{G(0)} = \frac{G(0)-1}{G(0)} = 1-\frac{1}{G(0)}. $$

This relation is exact for every \(d\ge3\). It also illustrates why the asymptotic formula is not a substitute for identities at short distances: the asymptotic describes targets far away, while this computation uses the one-step recursion.

What the Decay Does—and Does Not—Say

The power law \(|x|^{2-d}\) reflects the local quadratic behavior of \(1-\phi(\theta)\) near zero. The constant depends on the step distribution through that quadratic behavior; for this walk, the expansion is \(1-\phi(\theta)\sim|\theta|^2/(2d)\). The same analysis also clarifies the role of dimension: in \(d\ge3\), the singularity \(|\theta|^{-2}\) is integrable, and the Green function is finite.

A common mistake is to interpret \(G(x)\) itself as a hitting probability. It is an expected visit count, which can exceed one. The exact conversion for a single target is division by \(G(0)\), by the strong Markov property. Another mistake is to treat the asymptotic as an exact finite-distance formula. It determines the leading behavior as \(|x|\) grows; it does not generally provide exact values for nearby sites.

Check Your Understanding

Use the definitions and results above to answer these questions.

  1. What is the one-step characteristic function \(\phi(\theta)\) for simple random walk on \(\mathbb{Z}^d\)?
  2. Why is the singularity of \(1/(1-\phi(\theta))\) near zero of order \(|\theta|^{-2}\)?
  3. What is the leading constant in the Green-function asymptotic when \(d=3\)?
  4. How does the expected visit count \(G(x)\) determine the probability of ever hitting \(x\)?
  5. Why should the large-distance asymptotic not be treated as an exact formula for a nearby site?

Previous

Next

Back to Tutorials
Clinical Biostats