The Potential Kernel of the Two-Dimensional Lattice Walk

Why a Potential Kernel Is Needed in Two Dimensions

For a transient random walk, Green functions record finite expected visit counts and often directly describe hitting probabilities. The simple random walk on $\mathbb{Z}^2$, however, is recurrent: it returns to each site infinitely often with probability one. Its unrestricted Green function is therefore infinite, so subtracting or normalizing visit counts requires care.

The potential kernel provides a finite substitute. It compares the walk's return behavior from two different starting points. Its defining difference is finite even though the individual Green functions diverge, and the resulting function grows logarithmically with distance. That growth leads to explicit formulas for hitting one site before another.

Definition: Let $(S_n)_{n\geq 0}$ be simple random walk on $\mathbb{Z}^2$: at each step it moves with probability $1/4$ to each of its four nearest neighbors. Write $\mathbb{P}_x$ for its law when $S_0=x$, and set $\phi(t)=\tfrac12(\cos t_1+\cos t_2)$. The potential kernel is the function $a:\mathbb{Z}^2\to\mathbb{R}$ defined by $$ a(x)=\frac{1}{(2\pi)^2}\int_{[-\pi,\pi]^2} \frac{1-\cos(x\cdot t)}{1-\phi(t)}\,dt. $$ At $t=0$ the integrand may be assigned any value; this single point does not affect the integral.

The Discrete Poisson Equation

Write $P f(x)=\tfrac14\sum_{|e|=1}f(x+e)$ for the transition operator, where the sum is over the four unit coordinate vectors and their negatives. The potential kernel satisfies a simple equation that explains its role.

Theorem: For every $x\in\mathbb{Z}^2$, $$ Pa(x)-a(x)=\mathbf{1}_{\{x=0\}}. $$ Consequently, $a$ is harmonic at every nonzero site and has $Pa(0)=a(0)+1$.

Proof: Apply the transition operator inside the integral defining $a$. Averaging $\cos((x+e)\cdot t)$ over the four possible steps gives $\phi(t)\cos(x\cdot t)$; the sine terms cancel by symmetry. Therefore $$ Pa(x)-a(x) =\frac{1}{(2\pi)^2}\int_{[-\pi,\pi]^2}\cos(x\cdot t)\,dt. $$ The integral is $1$ when $x=0$ and $0$ for every other integer lattice point: each coordinate integral of $e^{i x_jt_j}$ over $[-\pi,\pi]$, divided by $2\pi$, is $1$ if $x_j=0$ and $0$ otherwise. This proves the identity.

The Fourier integral also shows why the kernel is a useful analogue of a Green function: its discrete Laplacian is concentrated at one site. The difference from a transient Green function is that the kernel remains finite in this recurrent setting.

Worked Example: The Value at a Nearest Neighbor

Let $e_1=(1,0)$ and $e_2=(0,1)$. At the origin, the Poisson equation gives $$ \frac{a(e_1)+a(-e_1)+a(e_2)+a(-e_2)}{4}=1. $$ Reflections and coordinate interchange preserve the walk and the defining integral. Hence the four neighboring values are equal. Their average is $1$, so each equals $1$. In particular, $a(e_1)=a(e_2)=1$. This calculation uses the kernel equation and symmetries; it does not require evaluating the Fourier integral directly.

Logarithmic Growth at Large Distances

Theorem: As $|x|\to\infty$ through lattice points, $$ a(x)=\frac{2}{\pi}\log |x|+O(1). $$ Here $|x|$ is Euclidean distance, and $O(1)$ means a quantity bounded uniformly in $x$.

Proof: Near the origin, Taylor expansion gives $$ 1-\phi(t)=\frac{|t|^2}{4}+O(|t|^4). $$ Choose a fixed disk $\{|t|\leq\delta\}$ contained in $[-\pi,\pi]^2$, with $\delta>0$ small. On this disk, $$ \frac{1}{1-\phi(t)}-\frac{4}{|t|^2}=O(1). $$ The contribution to the integral for $a(x)$ from replacing the reciprocal denominator by $4/|t|^2$ is bounded uniformly in $x$: the difference is bounded, and $|1-\cos(x\cdot t)|\leq 2$. The part of the original integral outside the disk is also uniformly bounded, because $1-\phi(t)$ is bounded away from zero there.

It remains to estimate the disk integral $$ \frac{4}{(2\pi)^2}\int_{|t|\leq\delta}\frac{1-\cos(x\cdot t)}{|t|^2}\,dt. $$ Put $R=|x|$ and use polar coordinates, rotating the angular variable so that $x\cdot t=Rr\cos\theta$. The integral without its prefactor becomes $$ \int_0^{\delta R}\left(2\pi-\int_0^{2\pi}\cos(s\cos\theta)\,d\theta\right)\frac{ds}{s}. $$ For $0<s\leq1$, the expression in parentheses is $O(s^2)$, since $1-\cos u\leq u^2/2$. For $s\geq1$, the angular oscillatory integral is $O(s^{-1/2})$. To see the source of this bound, split the angular domain into fixed neighborhoods of the stationary points of $\cos\theta$ and their complement. On the complement, integration by parts gives a bound of order $s^{-1}$; on each stationary-point neighborhood, the quadratic variation of $\cos\theta$ gives a bound of order $s^{-1/2}$ after rescaling distance from the stationary point by $s^{-1/2}$. Thus the angular integral divided by $s$ has a bounded integral over $s\geq1$. It follows that the displayed radial integral is $2\pi\log R+O(1)$ as $R\to\infty$. Multiplying by $4/(2\pi)^2$ gives $(2/\pi)\log R+O(1)$, as claimed.

Worked Example: Estimating the Kernel Far from the Origin

For a lattice point $x$ with $|x|=1000$, the theorem yields $$ a(x)=\frac{2}{\pi}\log(1000)+O(1). $$ The coefficient of the logarithm is about $0.637$, so the growing term is about $4.40$. The bounded error is independent of how far $x$ is from the origin; the theorem does not specify its exact value. In particular, the kernel grows without bound, but only logarithmically rather than linearly or quadratically.

Hitting One Site Before Another

For $y\in\mathbb{Z}^2$, define the hitting time $T_y=\inf\{n\geq0:S_n=y\}$. If $a\neq b$, set $T=\min(T_a,T_b)$. Two-dimensional simple random walk is recurrent, so $T$ is finite almost surely. The kernel gives the probability of which site is reached first.

Theorem: For distinct sites $a,b\in\mathbb{Z}^2$ and $x\notin\{a,b\}$, $$ \mathbb{P}_x(T_a<T_b) = \frac{a(x-b)-a(x-a)+a(a-b)}{2a(a-b)}. $$

Proof: Define $$ h(x)=\frac{a(x-b)-a(x-a)+a(a-b)}{2a(a-b)}. $$ The denominator is positive: the integral defining $a(a-b)$ has a nonnegative integrand that is positive on a set of positive area when $a-b\neq0$. By the Poisson equation, $h$ is harmonic away from $a$ and $b$, because the two translated kernel terms have their respective nonzero Laplacians only at those sites. At the endpoints, evenness and $a(0)=0$ give $h(a)=1$ and $h(b)=0$.

Moreover, $h$ is bounded on the lattice. Indeed, the logarithmic estimate gives $a(x-b)-a(x-a)=O(1)$ as $|x|\to\infty$, since $\log|x-b|-\log|x-a|$ is bounded there. On any finite set the function is bounded as well. Thus $h(S_{n\wedge T})$ is a bounded martingale: before $T$, harmonicity gives the martingale property, and after $T$ the process is stopped. Optional stopping at the bounded time $n\wedge T$ yields $\mathbb{E}_x[h(S_{n\wedge T})]=h(x)$. Since $T<\infty$ almost surely, bounded convergence as $n\to\infty$ gives $$ h(x)=\mathbb{E}_x[h(S_T)] =\mathbb{P}_x(T_a<T_b), $$ using the endpoint values $h(a)=1$ and $h(b)=0$. This proves the formula. $\square$

Worked Example: A Symmetric Starting Point

Let the two target sites be $a=-Ne_1$ and $b=Ne_1$, where $N\in\mathbb{N}$, and start at $x=0$. The distances from the starting point to the targets are equal, so $a(x-b)=a(Ne_1)=a(-Ne_1)=a(x-a)$. Also, $a(a-b)=a(-2Ne_1)=a(2Ne_1)$. Substitution gives $$ \mathbb{P}_0(T_{-Ne_1}<T_{Ne_1}) =\frac{0+a(2Ne_1)}{2a(2Ne_1)} =\frac12. $$ This agrees with reflection symmetry of the walk and verifies the hitting formula in a case where the answer is exact.

Worked Example: A Nearby Start and a Distant Target

Take $a=0$, $b=Ne_1$, and $x=e_1$, with $N\geq2$. The formula and the nearest-neighbor value $a(e_1)=1$ give $$ \mathbb{P}_{e_1}(T_0<T_{Ne_1}) = \frac{a((N-1)e_1)-1+a(Ne_1)}{2a(Ne_1)}. $$ For fixed start $e_1$, the logarithmic theorem gives $a(Ne_1)=\tfrac{2}{\pi}\log N+O(1)$ and $a((N-1)e_1)=\tfrac{2}{\pi}\log N+O(1)$. Consequently, $$ \mathbb{P}_{e_1}(T_0<T_{Ne_1}) =1+O\!\left(\frac{1}{\log N}\right) \longrightarrow 1. $$ The bounded errors need not be identical, so this estimate asserts convergence and its logarithmic scale, not an exact finite-$N$ probability. A recurrent walk can still be very likely to hit the nearby site first when the competing site is far away.

Interpretation and a Common Pitfall

The logarithmic kernel quantifies how slowly the two-dimensional walk escapes the influence of a site. In the hitting formula, the differences of kernel values encode the relative potential of the two targets, and the denominator normalizes the endpoint values to one and zero.

A common mistake is to treat recurrence as though it implied equal probabilities of hitting either site first. Recurrence says that each site is eventually visited, not that the first of two sites is equally likely to be visited. Equal probabilities follow from symmetry only in suitable configurations, such as the midpoint example. In general the starting point and the geometry of both targets matter through the full kernel formula.

Check Your Understanding

Try answering these questions using the definition, proofs, and examples above.

Why is the singularity in the Fourier definition of $a(x)$ integrable for each fixed $x$?
What is the value of $a(e_1)$, and which symmetry and kernel identity determine it?
Where does the coefficient $2/\pi$ in the logarithmic growth come from?
Why is the function used in the hitting-probability proof bounded, even though each kernel term grows logarithmically?
What additional symmetry makes the probability in the symmetric-start example equal to one half?

===