From Recurrence Tests to Hitting Questions
A recurrence criterion answers a broad question: does a walk return to its starting point? Potential theory makes that information more precise. It helps answer questions about a particular target, the chance of reaching it before leaving a region, and the number of visits one should expect.
The distinction between recurrence and expected visits is especially important. A recurrent walk returns to a point with probability one, but its expected total number of visits to that point is infinite. A transient walk, by contrast, has a finite expected number of visits, and its Green function gives both that expectation and the probability of ever hitting the point.
Walks, Green Functions, and Hitting Times
Let \(S_n\) be a random walk on \(\mathbb Z^d\) with independent, identically distributed increments, and write \(\mathbb P_x\) and \(\mathbb E_x\) for probability and expectation when \(S_0=x\). For a set \(A\subseteq\mathbb Z^d\), define its hitting time by \(T_A=\inf\{n\geq 0:S_n\in A\}\). For a point \(y\), the Green function is the expected number of visits to \(y\), including time zero:
The equality follows by applying monotone convergence to the partial sums of the nonnegative indicators. Thus \(G(x,y)\) may be infinite. For an irreducible walk, recurrence means that a point is revisited almost surely, while transience means that the expected number of visits to each point is finite.
To see the identity, if the walk ever hits \(y\), it has made no visits to \(y\) before its first hit. After that time, the strong Markov property gives an expected \(G(y,y)\) visits, counting the visit at the hitting time. If it never hits \(y\), it makes no visits. Therefore \(G(x,y)=\mathbb P_x(T_{\{y\}}<\infty)G(y,y)\).
The Fourier Recurrence Criterion
For a symmetric, irreducible lattice walk with characteristic function \(\phi(\theta)=\mathbb E_0[e^{i\theta\cdot(S_1-S_0)}]\), the Fourier recurrence criterion says that the walk is recurrent precisely when
For the simple nearest-neighbor walk on \(\mathbb Z^d\), each step is chosen uniformly from the \(2d\) coordinate directions, so \(\phi(\theta)=d^{-1}\sum_{j=1}^d\cos\theta_j\). Near the origin, \(1-\phi(\theta)\) is asymptotic to \(|\theta|^2/(2d)\). The local behavior of the integral is therefore that of \(\int_0^\delta r^{d-3}\,dr\): it diverges in dimensions one and two, and is finite in dimension three. Away from the origin the denominator is bounded away from zero. This predicts recurrence in dimensions one and two, and transience in dimension three.
Worked Example: Hitting the Origin on the Integer Line
Worked Example: Hitting the Origin on the Integer Line
Consider the symmetric nearest-neighbor walk on \(\mathbb Z\), started at \(x\neq 0\). Its characteristic function is \(\phi(\theta)=\cos\theta\). Since \(1-\cos\theta\sim\theta^2/2\) near zero, the Fourier integral diverges, and the walk is recurrent.
The one-dimensional potential kernel for this walk is \(a(x)=|x|\). Fix an integer \(R>|x|\) and stop the walk at \(\tau=T_{\{0\}}\wedge T_{\{|z|\geq R\}}\). At a nonzero state, \(|S_n|\) is harmonic: if \(z\geq1\), then \((|z-1|+|z+1|)/2=z\), and the same equality holds for \(z\leq-1\). Thus \(|S_{n\wedge\tau}|\) is a martingale. The stopping time is almost surely finite because the walk is in a finite interval until it exits, and the stopped values are bounded by \(R\), so optional stopping applies.
At a hit of zero the stopped value is zero; at an exit it is \(R\). Consequently,
Hence the probability of hitting zero before exiting is \(1-|x|/R\). Letting \(R\) increase gives probability one of eventually hitting zero: the events of hitting zero before exiting these expanding intervals increase to the event of ever hitting zero.
This probability-one result does not mean that the expected number of visits is finite. Recurrence implies \(G(0,0)=\infty\). In fact, the return probabilities satisfy \(\mathbb P_0(S_{2k}=0)=\binom{2k}{k}/4^k\sim 1/\sqrt{\pi k}\), while odd-time return probabilities vanish. Summing through time \(2N\) gives an expected number of visits asymptotic to \(2\sqrt{N/\pi}\), which grows without bound.
Worked Example: The Two-Dimensional Potential Kernel
Worked Example: The Two-Dimensional Potential Kernel
For simple nearest-neighbor walk on \(\mathbb Z^2\), \(\phi(\theta)=(\cos\theta_1+\cos\theta_2)/2\). Near zero, \(1-\phi(\theta)\sim|\theta|^2/4\), so the Fourier integral diverges logarithmically. The walk is recurrent.
The potential kernel can be defined by the Abel limit \(a(x)=\lim_{r\uparrow1}\sum_{n\geq0}r^n[\mathbb P_0(S_n=0)-\mathbb P_0(S_n=x)]\). For this walk, it is harmonic away from the origin and has the large-distance estimate \(a(x)=(2/\pi)\log|x|+O(1)\). These properties let us estimate the chance of hitting zero before leaving a large disk, without pretending that the potential kernel is constant along the disk's boundary.
Let \(D_R=\{z\in\mathbb Z^2:|z|<R\}\), take \(x\in D_R\setminus\{0\}\), and set \(\tau=T_{\{0\}}\wedge T_{D_R^c}\). The potential kernel is harmonic at every nonzero state before \(\tau\). The stopped process \(a(S_{n\wedge\tau})\) is therefore a martingale. Since the walk is stopped on exiting a finite set or hitting zero, \(\tau\) is almost surely finite; its stopped positions lie in a finite set, so the martingale is bounded and optional stopping applies.
On hitting zero, the potential kernel has value \(a(0)=0\). On exit, the position has distance between \(R\) and \(R+1\), and the asymptotic estimate gives \(a(S_\tau)=(2/\pi)\log R+O(1)\), uniformly over possible exit sites. Thus
and the conditional expectation on the right is \((2/\pi)\log R+O(1)\). It follows that
This is a finite-domain estimate whose limit recovers almost-sure hitting. The denominator grows logarithmically, so the chance of exiting without first hitting zero decreases on the order of \(1/\log R\).
The expected number of visits, however, is infinite. Indeed, for \(k\geq0\), \(\mathbb P_0(S_{2k}=0)=\binom{2k}{k}^2/16^k\sim1/(\pi k)\), and odd-time return probabilities vanish. The expected number of visits through time \(2N\) is therefore asymptotic to \((1/\pi)\log N\), and \(G(0,0)=\infty\).
Worked Example: Hitting the Origin in Three Dimensions
Worked Example: Hitting the Origin in Three Dimensions
For simple nearest-neighbor walk on \(\mathbb Z^3\), \(\phi(\theta)=(\cos\theta_1+\cos\theta_2+\cos\theta_3)/3\). Near zero, \(1-\phi(\theta)\sim|\theta|^2/6\). The recurrence integral has local radial behavior \(\int_0^\delta r^2/r^2\,dr\), which is finite. There are no other singularities where \(\phi=1\), so the walk is transient.
The Green function at the origin has the Fourier representation
The standard transient Green-function asymptotic for this walk is \(G(x,0)\sim 3/(2\pi|x|)\) as \(|x|\to\infty\). Applying the Green-function hitting identity gives
Thus the walk has a positive chance of avoiding the origin forever, and the chance of ever hitting it decreases proportionally to the reciprocal of the starting distance. The expected number of visits to the origin is exactly \(G(x,0)\), so it has the same \(1/|x|\) large-distance order. If the walk starts at zero, its expected total number of visits is the finite number \(G(0,0)\).
What These Examples Show
The three examples illustrate how the same tools lead to different conclusions. In one and two dimensions, recurrence forces eventual hitting of any fixed point for these irreducible walks, but the expected number of visits is infinite. The potential kernel refines the recurrence statement by quantifying how likely it is to hit a target before leaving a large finite region. In three dimensions, transience makes the Green function finite, and the ratio of Green functions gives an exact hitting probability.
Check Your Understanding
Use the recurrence criteria, potential kernels, and Green-function identities to answer these questions.
- Why does the Fourier recurrence integral diverge for the two-dimensional simple walk?
- For the one-dimensional walk started at \(x\) with \(0<|x|<R\), what is the probability of hitting zero before exiting \((-R,R)\)?
- What is the large-\(R\) order of the two-dimensional probability of exiting a disk before hitting the origin?
- Why can a recurrent walk have an infinite expected number of visits even though it hits the target almost surely?
- For a transient walk, how do \(G(x,y)\) and \(G(y,y)\) determine the probability of ever hitting \(y\)?