Tutorials › Probability Theory (Graduate) › Fourier Recurrence Criterion for Lattice Walks

Home  /  Tutorials  /  Random Walks and Potential Theory

Random Walks and Potential Theory · Tutorial 933 of 946

Fourier Recurrence Criterion for Lattice Walks

Learn how Fourier inversion turns expected return counts into an integral, and how the singularity of that integral determines recurrence for symmetric lattice walks.

Advanced 12 min read

What You'll Learn

  • Define the characteristic function of a symmetric lattice step distribution
  • Relate recurrence to the total expected number of returns
  • Derive the Fourier integral criterion using Fourier inversion and Abel limits
  • Evaluate the criterion for the one-dimensional simple walk
  • Determine the recurrence threshold for coordinate simple walks on the integer lattice
  • See why adding holding probability need not change recurrence

Why Fourier Analysis Detects Recurrence

A translation-invariant random walk on the lattice has the same step distribution at every location. Its long-term return behavior is encoded in the probabilities of being back at the origin after \(n\) steps. Fourier analysis provides a way to combine all of these probabilities into one integral: the characteristic function of a single step is raised to the \(n\)th power, and the resulting integral detects whether the total expected number of returns is finite or infinite.

We develop the criterion for symmetric step distributions. Symmetry makes the characteristic function real-valued and lets us handle its possible negative values directly. This assumption matters: for a nonsymmetric step distribution the characteristic function can be complex, so the integral must be interpreted differently.

Setup: Let \((S_n)_{n\in\mathbb{N}_0}\) be a random walk on \(\mathbb{Z}^d\), with \(S_0=0\), whose independent increments have common distribution \(\mu\). Thus \(S_n=X_1+\cdots+X_n\), where \(\mathbb{P}(X_k=x)=\mu(x)\). We assume \(\mu(x)=\mu(-x)\) for every \(x\in\mathbb{Z}^d\). Write \(p_n(0)=\mathbb{P}(S_n=0)\).

The characteristic function of one step, evaluated at \(\theta\in[-\pi,\pi]^d\), is

$$ \phi(\theta)=\mathbb{E}\!\left[e^{i\theta\cdot X_1}\right] =\sum_{x\in\mathbb{Z}^d}\mu(x)e^{i\theta\cdot x}. $$

Symmetry pairs the terms for \(x\) and \(-x\), so the imaginary parts cancel. In particular, \(\phi\) is real-valued, and \(-1\leq\phi(\theta)\leq 1\). We use normalized Lebesgue measure on the torus: an integral over \([-\pi,\pi]^d\) is multiplied by \((2\pi)^{-d}\).

Returns and Expected Visit Counts

For a walk started at the origin, define its first return time by \(\tau=\inf\{n\geq 1:S_n=0\}\), with \(\tau=\infty\) if the walk never returns. The walk is recurrent at the origin when \(\mathbb{P}(\tau<\infty)=1\). The expected total number of visits to the origin, counting the visit at time zero, is the Green function at the origin:

$$ G(0,0)=\sum_{n=0}^{\infty}p_n(0). $$
Proposition: The walk is recurrent at the origin if and only if \(G(0,0)=\infty\).
Proof. Let \(f=\mathbb{P}(\tau<\infty)\). After each return to the origin, the independent-increments property gives the same probability \(f\) of another return. Consequently, the probability of at least \(k\) returns after time zero is \(f^k\). If \(N\) is the total number of visits, including time zero, then $$ \mathbb{E}[N]=\sum_{k=0}^{\infty}\mathbb{P}(N\geq k+1) =\sum_{k=0}^{\infty}f^k. $$ This series is infinite exactly when \(f=1\), which is precisely recurrence. On the other hand, writing \(N=\sum_{n=0}^{\infty}\mathbf{1}_{\{S_n=0\}}\) and taking expectations of the increasing partial sums gives \(\mathbb{E}[N]=\sum_{n=0}^{\infty}p_n(0)=G(0,0)\). Thus recurrence is equivalent to divergence of the Green function. \(\square\)

Fourier Inversion and the Recurrence Criterion

The lattice Fourier inversion formula says that the probability that a lattice-valued random variable equals zero is the normalized integral of its characteristic function. Since the characteristic function of a sum of \(n\) independent increments is \(\phi(\theta)^n\), we obtain

$$ p_n(0)=\frac{1}{(2\pi)^d}\int_{[-\pi,\pi]^d}\phi(\theta)^n\,d\theta. $$

For a fixed \(n\), this identity is valid even when \(\phi\) takes negative values: the integral as a whole is the nonnegative probability \(p_n(0)\). To sum over \(n\), first insert a factor \(r^n\) with \(0<r<1\). The geometric series then converges uniformly because \(|r\phi(\theta)|\leq r<1\), so summation and integration can be interchanged.

Theorem (Fourier recurrence criterion for symmetric lattice walks): Under the setup above, the walk is recurrent at the origin if and only if $$ \frac{1}{(2\pi)^d}\int_{[-\pi,\pi]^d}\frac{d\theta}{1-\phi(\theta)}=\infty. $$ The integrand is nonnegative; at a point where \(\phi(\theta)=1\), it is understood as \(+\infty\).
Proof. For \(0<r<1\), Fourier inversion and the uniformly convergent geometric series give $$ \sum_{n=0}^{\infty}r^n p_n(0) =\frac{1}{(2\pi)^d}\int_{[-\pi,\pi]^d} \frac{d\theta}{1-r\phi(\theta)}. $$ The left side increases to \(G(0,0)\) as \(r\) increases to \(1\), because every \(p_n(0)\) is nonnegative. We analyze the right side by splitting the torus into the sets where \(\phi\geq 0\) and \(\phi<0\). Where \(\phi\geq0\), the functions \(1/(1-r\phi)\) increase pointwise as \(r\) increases to \(1\). Their limit is \(1/(1-\phi)\), including the value \(+\infty\) when \(\phi=1\). The monotone convergence theorem therefore shows that the integrals over this set increase to the integral of \(1/(1-\phi)\) there. Where \(\phi<0\), we have \(1\leq 1-r\phi\leq 1+r<2\), so \(0<1/(1-r\phi)\leq1\). The contribution from that set is bounded uniformly in \(r\); its limiting integrand \(1/(1-\phi)\) is also bounded there. Thus the Abel integrals diverge exactly when the full integral of \(1/(1-\phi)\) diverges. By the proposition, \(G(0,0)=\infty\) exactly when the walk is recurrent. \(\square

Worked Example: The Symmetric Simple Walk on \(\mathbb{Z}\)

Worked Example: The Symmetric Simple Walk on \(\mathbb{Z}\)

At each step the walk moves \(+1\) or \(-1\), each with probability \(1/2\). Its characteristic function is $$ \phi(\theta)=\frac{e^{i\theta}+e^{-i\theta}}{2}=\cos\theta. $$ The recurrence integral is therefore $$ \frac{1}{2\pi}\int_{-\pi}^{\pi}\frac{d\theta}{1-\cos\theta}. $$ For \(0<|\theta|\leq\pi\), the identity \(1-\cos\theta=2\sin^2(\theta/2)\) holds. Since \(|\sin u|\leq |u|\), we have \(1-\cos\theta\leq \theta^2/2\), and hence \(1/(1-\cos\theta)\geq2/\theta^2\). The integral of \(2/\theta^2\) diverges in every neighborhood of zero. The recurrence criterion shows that the walk is recurrent.

Worked Example: Coordinate Simple Walks in Higher Dimensions

Worked Example: Coordinate Simple Walks in Higher Dimensions

For the coordinate simple walk on \(\mathbb{Z}^d\), each of the \(2d\) steps \(+e_j\) and \(-e_j\), \(1\leq j\leq d\), has probability \(1/(2d)\). Its characteristic function is $$ \phi(\theta)=\frac{1}{d}\sum_{j=1}^d\cos\theta_j, \qquad 1-\phi(\theta)=\frac{1}{d}\sum_{j=1}^d(1-\cos\theta_j). $$ On the torus, \(\phi(\theta)=1\) only when every coordinate is \(0\) modulo \(2\pi\), so the only singularity is at the origin. Near zero, the elementary sine bounds \(2|u|/\pi\leq|\sin u|\leq|u|\) for \(|u|\leq\pi/2\) imply $$ \frac{2}{\pi^2}\theta_j^2\leq 1-\cos\theta_j\leq\frac{\theta_j^2}{2}. $$ Summing over \(j\) shows that \(1-\phi(\theta)\) is bounded above and below by positive constants times \(\|\theta\|^2=\sum_{j=1}^d\theta_j^2\) near zero. Thus the recurrence integral has the same convergence behavior there as the integral of \(\|\theta\|^{-2}\). In dimension \(d\), its radial behavior is $$ \int_0^\delta r^{d-1}r^{-2}\,dr =\int_0^\delta r^{d-3}\,dr. $$ This diverges for \(d=1\) and \(d=2\), and is finite for \(d\geq3\). Away from the origin the integrand is bounded, so it creates no other divergence. Therefore the coordinate simple walk is recurrent in dimensions one and two, and transient in dimensions three and higher.

Worked Example: A Lazy Walk on the Integer Line

Worked Example: A Lazy Walk on the Integer Line

Now let the walk on \(\mathbb{Z}\) stay in place with probability \(1/2\), and move \(+1\) or \(-1\) with probability \(1/4\) each. Its characteristic function is $$ \phi(\theta)=\frac12+\frac14e^{i\theta}+\frac14e^{-i\theta} =\frac{1+\cos\theta}{2}. $$ Consequently, $$ 1-\phi(\theta)=\frac{1-\cos\theta}{2}. $$ The recurrence integral is twice the integral for the symmetric simple walk on \(\mathbb{Z}\), and therefore diverges at zero. This lazy walk is recurrent as well. The holding probability changes the timing of the walk but, in this example, does not remove the singularity that determines recurrence.

Reading the Criterion Carefully

The criterion identifies recurrence through the behavior of the characteristic function near points where it equals one. For the coordinate simple walk, the only such point on the torus is the origin, and the local quadratic behavior of \(1-\phi(\theta)\) makes dimension decisive. More generally, the integral must be checked over the entire torus: if there are other points where \(\phi=1\), their neighborhoods can contribute additional singularities.

A common error is to treat \(\phi\) as though it were always nonnegative. Even for a symmetric walk, its characteristic function may be negative on part of the torus. The proof handles that region separately: when \(\phi<0\), the integrand \(1/(1-r\phi)\) stays bounded as \(r\) approaches one, so it cannot cause divergence. The potential divergence comes from where \(\phi\) approaches one.

Symmetry is also a real hypothesis, not just a convenient notation choice. Without symmetry, \(\phi\) can be complex, and the displayed real-valued integral criterion does not apply in this form. A nonsymmetric walk requires a version that accounts for the real part of its characteristic function. The preceding criterion should therefore be used only under its stated symmetry assumption.

Check Your Understanding

Use the definitions and criterion above to answer the following questions.

  1. Why does Fourier inversion express \(p_n(0)\) as the integral of \(\phi(\theta)^n\)?
  2. What role does the factor \(r^n\) play when deriving the integral formula for the sum of return probabilities?
  3. Why can the region where \(\phi<0\) not cause divergence in the recurrence criterion?
  4. For the coordinate simple walk, what feature of \(1-\phi(\theta)\) near the origin produces the dimension threshold?
  5. Which assumption in the theorem ensures that \(\phi\) is real-valued?

Previous

Next

Back to Tutorials
Clinical Biostats