Classifying Lattice Walks with Return Data

Return Data as a Classification Tool

For a lattice walk, the long-term question is often not the exact position at every time but whether the walk returns to its starting point. Return probabilities provide one route to the answer: if their sum is finite, the expected number of visits is finite, and return cannot occur with probability one. A second route uses the first return time, which separates visits into successive excursions. Fourier symbols make these tests practical for walks whose step distributions are symmetric but whose coordinate directions need not have equal probabilities.

Throughout, let \((\Omega,\mathcal{F},\mathbb{P})\) be a probability space and let \((X_n)_{n\ge0}\) be a time-homogeneous random walk on \(S=\mathbb{Z}^d\), with \(X_0=0\) and independent, identically distributed increments. Write \(u_n=\mathbb{P}_0(X_n=0)\), where \(\mathbb{P}_0\) denotes the law started at the origin. Its first return time is \(T_0^+=\inf\{n\ge1:X_n=0\}\). The walk is recurrent at the origin if \(\mathbb{P}_0(T_0^+<\infty)=1\), and transient at the origin if this probability is less than \(1\). For the translation-invariant walks considered here, the same classification applies at every lattice point.

Definition: The Green function at the origin is \(G(0,0)=\sum_{n=0}^{\infty}u_n\), with the value \(+\infty\) allowed. It is the expected total number of visits to the origin, counting time \(0\): indeed, the number of such visits is \(\sum_{n\ge0}\mathbf{1}_{\{X_n=0\}}\), whose expectation is \(\sum_{n\ge0}u_n\) by monotone convergence.

Theorem (Return criterion): For a time-homogeneous random walk started at the origin, \(G(0,0)=\infty\) if and only if the walk is recurrent at the origin. Equivalently, \(G(0,0)<\infty\) if and only if the walk is transient there.

Proof. Set \(f_k=\mathbb{P}_0(T_0^+=k)\) for \(k\ge1\), and \(F(s)=\sum_{k\ge1}f_ks^k\), \(U(s)=\sum_{n\ge0}u_ns^n\) for \(0\le s<1\). To be at the origin at time \(n\ge1\), the walk must first return at some time \(k\le n\), and then be at the origin \(n-k\) steps after that return. By the Markov property and time homogeneity, \(u_n=\sum_{k=1}^n f_ku_{n-k}\). Multiplying by \(s^n\) and summing gives \(U(s)-1=F(s)U(s)\); these series converge absolutely for \(s<1\), since their coefficients are probabilities. Thus \(U(s)=1/(1-F(s))\). As \(s\) increases to \(1\), monotone convergence gives \(U(s)\to G(0,0)\) and \(F(s)\to\sum_{k\ge1}f_k=\mathbb{P}_0(T_0^+<\infty)\). Therefore \(G(0,0)=\infty\) exactly when \(\sum_k f_k=1\), which is recurrence by definition. If the return probability is less than \(1\), the identity gives the finite limit \(G(0,0)=1/(1-\sum_k f_k)\). \(\square\)

This criterion makes exact return counts useful: one need not calculate the entire first-return distribution if the sum of the return probabilities can be classified. For symmetric finite-range walks, a Fourier symbol often gives that sum. If a single step has distribution \(a(z)=\mathbb{P}(X_1=z\mid X_0=0)\), define its symbol on \([-\pi,\pi]^d\) by \(\phi(\theta)=\sum_z a(z)e^{i z\cdot\theta}\). For symmetric steps, \(\phi\) is real and equals \(\sum_z a(z)\cos(z\cdot\theta)\).

Fourier test: Suppose the step distribution is symmetric and has finite support. Fourier inversion gives \(u_n=(2\pi)^{-d}\int_{[-\pi,\pi]^d}\phi(\theta)^n\,d\theta\). Consequently, if \((1-\phi)^{-1}\) is integrable on this cube, then \(G(0,0)<\infty\); if its integral is infinite, then \(G(0,0)=\infty\). Values at isolated points where \(\phi=1\) are interpreted through the surrounding integral.

Justification of the Fourier test. For \(0\le r<1\), Fourier inversion and the uniformly convergent geometric series give \(\sum_{n\ge0}r^nu_n=(2\pi)^{-d}\int(1-r\phi(\theta))^{-1}\,d\theta\). The left side increases to \(G(0,0)\) as \(r\) increases to \(1\). Where \(\phi<0\), the integrand on the right is at most \(1\); where \(0\le\phi<1\), it is at most \((1-\phi)^{-1}\). Thus if \((1-\phi)^{-1}\) is integrable, dominated convergence shows the right side has a finite limit. If the integral of \((1-\phi)^{-1}\) is infinite, Fatou's lemma applied to the nonnegative integrands shows the limiting left side is infinite. This proves both implications. The Fourier inversion formula used here is the standard lattice Fourier inversion result.

Exact Returns in One and Two Dimensions

Worked Example: The One-Dimensional Simple Symmetric Walk

Let \(S=\mathbb{Z}\), with one-step transitions from each \(i\) to \(i-1\) and \(i+1\), each with probability \(\tfrac12\). The two probabilities in every row sum to \(\tfrac12+\tfrac12=1\). A return is possible only after an even number of steps. In \(2n\) steps, returning to \(0\) requires exactly \(n\) steps in each direction, so

u_{2n}=\binom{2n}{n}\left(\frac12\right)^{2n} =\frac{\binom{2n}{n}}{4^n},\qquad u_{2n+1}=0.

For instance, \(u_2=\binom21/4=2/4=\tfrac12\), and \(u_4=\binom42/16=6/16=\tfrac38\). By Stirling's formula, \(\binom{2n}{n}/4^n\sim 1/\sqrt{\pi n}\). The comparison series \(\sum_{n\ge1}n^{-1/2}\) diverges, so \(\sum_m u_m=\infty\) and the return criterion gives recurrence. The period is \(2\), but this does not alter the recurrence classification.

Check: The first two possible return probabilities sum with \(u_0=1\) to \(1+\tfrac12+\tfrac38=\tfrac{15}{8}\); later even-time terms are positive as well. The central-binomial asymptotic shows that the full series diverges, rather than merely establishing that its first few terms are positive.

Worked Example: The Two-Dimensional Simple Symmetric Walk

On \(S=\mathbb{Z}^2\), let each of the four moves \((1,0),(-1,0),(0,1),(0,-1)\) have probability \(\tfrac14\). Their probabilities sum to \(4\cdot\tfrac14=1\). To return after \(2n\) steps, the walk must make \(k\) right moves and \(k\) left moves, and \(n-k\) upward moves and \(n-k\) downward moves, for some \(k\in\{0,\ldots,n\}\). The number of paths for this choice is \((2n)!/[k!^2(n-k)!^2]\). Hence

u_{2n}=\frac{(2n)!}{4^{2n}}\sum_{k=0}^n\frac{1}{k!^2(n-k)!^2} =\frac{\binom{2n}{n}^2}{4^{2n}}, \qquad u_{2n+1}=0.

For the identity, write each summand as \(\binom{n}{k}^2/(n!)^2\). The sum of these squared binomial coefficients is \(\binom{2n}{n}\), by comparing the coefficient of \(x^n\) in \((1+x)^n(1+x)^n\). Thus \(u_2=\binom21^2/16=\tfrac14\), while \(u_4=\binom42^2/256=36/256=\tfrac9{64}\). Stirling's formula gives \(u_{2n}\sim 1/(\pi n)\), and the harmonic series diverges. Therefore the walk is recurrent.

Check: At two steps, the walk returns exactly when its second move reverses its first; there are four such two-step paths among \(4^2=16\), giving \(u_2=4/16=\tfrac14\), as in the formula. The \(1/n\) asymptotic establishes divergence of the full return sum.

Fourier Symbols: Laziness and Anisotropy

Worked Example: A Lazy Walk on the Two-Dimensional Lattice

On \(\mathbb{Z}^2\), let the walk stay in place with probability \(\tfrac12\) and take each of the four nearest-neighbor steps with probability \(\tfrac18\). The row sum is \(\tfrac12+4\cdot\tfrac18=1\). The simple walk's symbol is \(\phi(\theta)=\tfrac12(\cos\theta_1+\cos\theta_2)\), so the lazy walk's symbol is \(\phi_L(\theta)=\tfrac12+\tfrac12\phi(\theta)\). In particular,

1-\phi_L(\theta)=\tfrac12(1-\phi(\theta)).

Near \((0,0)\), \(1-\cos x\sim x^2/2\), so \(1-\phi(\theta)\sim(\theta_1^2+\theta_2^2)/4\). The reciprocal therefore has the same local behavior as a positive constant times \((\theta_1^2+\theta_2^2)^{-1}\). In two dimensions its integral diverges logarithmically: in polar coordinates the local radial contribution is proportional to \(\int_0^\epsilon r^{-1}\,dr=\infty\). The Fourier test gives recurrence. The factor of \(2\) in \((1-\phi_L)^{-1}=2(1-\phi)^{-1}\) changes the Green integral's size but not whether it is finite.

Check: The probability of being at the origin after one step is \(u_1=\tfrac12\), precisely the holding probability. This odd-time return is consistent with the lazy walk's definition and does not remove the logarithmic divergence at the symbol's singular point.

Worked Example: An Anisotropic Walk in Two Dimensions

Let the walk on \(\mathbb{Z}^2\) take each horizontal step \((\pm1,0)\) with probability \(\tfrac16\), and each vertical step \((0,\pm1)\) with probability \(\tfrac13\). The total probability is \(2\cdot\tfrac16+2\cdot\tfrac13=\tfrac13+\tfrac23=1\). The walk is symmetric under reversing any step, and its symbol is

\phi_A(\theta)=\tfrac13\cos\theta_1+\tfrac23\cos\theta_2.

Since each cosine is at most \(1\), \(\phi_A=1\) only when both coordinates are \(0\) modulo \(2\pi\). Near the origin, the expansion \(1-\cos x\sim x^2/2\) gives \(1-\phi_A(\theta)\sim\tfrac16\theta_1^2+\tfrac13\theta_2^2\). This quadratic form is bounded above and below by positive multiples of \(\theta_1^2+\theta_2^2\): its coefficients are \(\tfrac16\) and \(\tfrac13\). Thus the reciprocal has the same two-dimensional logarithmic divergence as in the preceding example. Away from the origin, continuity and the unique maximum property make \(1-\phi_A\) bounded away from zero on any closed region not containing the origin. The Fourier test therefore gives recurrence.

Check: The coefficient comparison uses the actual parameters: \(\tfrac16(\theta_1^2+\theta_2^2)\le\tfrac16\theta_1^2+\tfrac13\theta_2^2\le\tfrac13(\theta_1^2+\theta_2^2)\). Both bounds yield the same divergent radial integral in dimension two.

Worked Example: The Three-Dimensional Simple Symmetric Walk

On \(\mathbb{Z}^3\), assign probability \(\tfrac16\) to each of the six moves \(\pm e_1,\pm e_2,\pm e_3\). The row sum is \(6\cdot\tfrac16=1\). The symbol is \(\phi_3(\theta)=\tfrac13(\cos\theta_1+\cos\theta_2+\cos\theta_3)\). It equals \(1\) only at the origin modulo \(2\pi\), and near that point

1-\phi_3(\theta)\sim\frac{\theta_1^2+\theta_2^2+\theta_3^2}{6}.

Consequently, near the origin the Green integrand is bounded above by a constant times \((\theta_1^2+\theta_2^2+\theta_3^2)^{-1}\). Its local integral is bounded by a constant times \(\int_0^\epsilon r^2/r^2\,dr=\epsilon\), which is finite. Outside a neighborhood of the origin the denominator is bounded away from zero, so the integral over the rest of the cube is finite too. The Fourier test gives \(G(0,0)<\infty\), hence transience.

Check: The dimension changes the local radial power: in three dimensions it is \(r^2/r^2=1\), whereas in two dimensions it is \(r/r^2=1/r\). The former is integrable at zero and the latter is not.

Interpreting the Classification

These examples show how the same criterion can be used with different kinds of return data. Exact counts yield explicit \(u_n\) and an asymptotic comparison; the Fourier symbol reduces the issue to the singularity of \((1-\phi)^{-1}\). For symmetric nearest-neighbor walks with nondegenerate coordinate probabilities, the local behavior is quadratic in the displacement from the origin. The radial integral then has the form \(\int_0^\epsilon r^{d-3}\,dr\): it diverges in dimensions one and two and is finite in dimensions three and above. This local calculation must be combined with a check that there are no other points on the Fourier torus where \(\phi=1\).

Common mistake. A divergent Fourier integral is not evidence that the walk is transient. It means \(G(0,0)=\infty\), and the return criterion then gives recurrence. For example, in the two-dimensional simple walk, the local integrand behaves like \(1/(\theta_1^2+\theta_2^2)\), whose radial integral is \(\int_0^\epsilon r^{-1}\,dr=\infty\); the correct conclusion is recurrence. Another error is to assume laziness changes the dimension threshold: in the lazy example, it multiplies \(1-\phi\) by \(\tfrac12\), leaving integrability unchanged. Finally, an anisotropic quadratic form must be checked to remain nondegenerate. If a step distribution cannot move in some lattice directions, the effective dimension may differ from the ambient dimension, and the preceding full-dimensional comparison does not apply without adjustment.

Check Your Understanding

For each question, state which return criterion or local comparison you use, and distinguish a finite Green function from a divergent one.

For the one-dimensional simple symmetric walk, why do odd-time return probabilities vanish, and why does the even-time series nevertheless diverge?
For a symmetric finite-range walk, explain how the first-return probabilities \(f_k\) determine whether \(G(0,0)\) is finite.
A two-dimensional lazy walk has symbol \(\phi_L=\tfrac12+\tfrac12\phi\). What happens to the integrability of \((1-\phi)^{-1}\) when it is replaced by \((1-\phi_L)^{-1}\)?
For the anisotropic example, identify the two positive coefficients in the quadratic approximation to \(1-\phi_A\). Why do they not change the recurrence classification?
In the three-dimensional example, what radial power appears in the local Green integral, and is its integral finite at zero?