Potential Kernels for Recurrent Walks on the Line

Why a Potential Kernel Is Useful

A centered random walk on the integer line is recurrent under the assumptions used here, so it eventually visits every site. Yet its expected total number of visits to a site is infinite. Green functions therefore cannot directly measure the relative likelihood of reaching one site before another.

The potential kernel replaces an infinite expected visit count by a difference of two such counts. That difference remains finite, and its spatial differences provide a harmonic function away from specified target sites. This lets us calculate hitting probabilities even when a walk can jump over intermediate locations.

Setting and Definition

Let $X_1,X_2,\ldots$ be independent identically distributed integer-valued random variables, and write $S_0=0$ and $S_n=X_1+\cdots+X_n$. Assume that the walk is irreducible on $\mathbb Z$, that $\mathbb E[X_1]=0$, and that $0<\mathbb E[X_1^2]=\sigma^2<\infty$. Irreducibility means that every integer is reachable from every other integer with positive probability in some number of steps. Under these assumptions the walk is recurrent.

Let $p_n(y)=\mathbb P(S_n=y)$. For $0<r<1$, define the Abel-regularized Green-function difference by

a_r(x)=\sum_{n=0}^{\infty}r^n\bigl(p_n(0)-p_n(-x)\bigr).

The factor $r^n$ makes both Green-function sums finite separately. Their difference has a finite limit as $r$ increases to $1$.

Definition: The potential kernel of this walk is the function $a:\mathbb Z\to\mathbb R$ defined by $a(x)=\lim_{r\uparrow1}a_r(x)$. In particular, $a(0)=0$.

Fourier Construction and Basic Properties

Let $\phi(t)=\mathbb E[e^{itX_1}]$ be the characteristic function of one step. Fourier inversion gives $p_n(-x)=(2\pi)^{-1}\int_{-\pi}^{\pi}e^{itx}\phi(t)^n\,dt$. Consequently, for $r<1$,

a_r(x)=\frac{1}{2\pi}\int_{-\pi}^{\pi} \frac{1-e^{itx}}{1-r\phi(t)}\,dt.

Because the walk is irreducible, $\phi(t)=1$ on $[-\pi,\pi]$ only at $t=0$. At that point, centering and finite variance give $\phi(t)=1-\sigma^2t^2/2+o(t^2)$. The numerator vanishes at $t=0$; its first-order term is odd and imaginary. Taking the symmetric limit of the integral therefore yields a finite value for each fixed integer $x$.

We will also use a standard one-dimensional potential-kernel estimate: for fixed integers $u,v$, the differences $a(x-u)-a(x-v)$ are bounded as $x$ ranges over $\mathbb Z$; moreover $a(x)=O(1+|x|)$. These estimates follow by separating the $t^{-2}$ singularity of $1/(1-\phi(t))$ near zero in the Fourier representation and applying the symmetric Dirichlet estimate to the resulting first-order singularity. The finite-variance assumption gives the stated local expansion at zero. In particular, the estimate applies to every fixed difference used below.

Worked Example: The Symmetric Simple Walk

For steps $X_1=1$ and $X_1=-1$, each with probability $1/2$, $\phi(t)=\cos t$. The Fourier representation becomes

a(x)=\frac{1}{2\pi}\int_{-\pi}^{\pi} \frac{1-e^{itx}}{1-\cos t}\,dt =\frac{1}{2\pi}\int_{-\pi}^{\pi} \frac{1-\cos(xt)}{1-\cos t}\,dt.

The imaginary part integrates to zero because it is odd. For $x\ge1$, the identity $\sin(xt/2)/\sin(t/2)=\sum_{j=0}^{x-1}e^{i(j-(x-1)/2)t}$ shows that the integral of its squared absolute value over $[-\pi,\pi]$ is $2\pi x$: all cross terms with distinct integer frequencies integrate to zero. Since $(1-\cos(xt))/(1-\cos t)$ is that squared absolute value, $a(x)=x$. The integrand depends only on $|x|$, so $a(x)=|x|$ for every integer $x$.

Worked Example: A Lazy Symmetric Walk

Suppose the walk moves one unit in either direction with probability $q$ each, and stays put with probability $1-2q$, where $0<q\le1/2$. Its mean is zero and its variance is $\sigma^2=2q$. Its characteristic function satisfies $1-\phi(t)=2q(1-\cos t)$. Thus the same integral calculation gives

a(x)=\frac{1}{2q}\,|x|=\frac{|x|}{\sigma^2}.

For example, when $q=1/4$, $a(3)=6$. The larger value than in the non-lazy simple walk reflects the fact that this walk accumulates fewer spatial moves per unit time; the kernel’s normalization is consistent with its variance.

The Potential-Kernel Equation

Write $Pa(x)=\mathbb E[a(x+X_1)]$ for the one-step transition operator applied to $a$. The potential kernel satisfies an equation with a unit source at the origin.

Theorem: For every $x\in\mathbb Z$, $$ Pa(x)-a(x)=\mathbf 1_{\{x=0\}}. $$

Proof. First use the Abel-regularized kernel. Since one step followed by $n$ further steps has the law of $S_{n+1}$, $$ \mathbb E[a_r(x+X_1)]-a_r(x) =\sum_{n\ge0}r^n\bigl(p_n(-x)-p_{n+1}(-x)\bigr). $$ Telescoping gives the exact identity $$ \mathbb E[a_r(x+X_1)]-a_r(x) =\mathbf 1_{\{x=0\}}-(1-r)\sum_{m\ge1}r^{m-1}p_m(-x). $$ The correction has a minus sign. For fixed $x$, recurrence on the infinite irreducible state space implies $p_m(-x)\to0$. The correction therefore tends to zero: it is $1-r$ times an Abel average of a bounded sequence tending to zero. The Fourier estimates above give $a_r(y)\to a(y)$ and a bound $C(1+|y|)$, uniform in $r$, for a finite constant $C$. Since $\mathbb E|X_1|<\infty$, dominated convergence applies to the expectation over $x+X_1$. Letting $r\uparrow1$ proves the equation. $\square$

In particular, $a$ is harmonic at every $x\ne0$: its expected value after one step equals its current value there. At the origin the equation has a positive unit source. Keeping this sign straight is essential when constructing a hitting-probability function.

Two-Sided Hitting Probabilities

For a starting site $x$ and a target site $c$, let $T_c=\inf\{n\ge0:x+S_n=c\}$. For distinct sites $a$ and $b$, recurrence and irreducibility imply that $T_a\wedge T_b$ is finite almost surely. Define $D=a(b-a)+a(a-b)$, where the $a(\cdot)$ on the right denotes the potential kernel, not a target site.

Theorem: For distinct integers $a,b$, $D>0$, and for every starting site $x$, $$ \mathbb P_x(T_b<T_a) = \frac{a(x-a)-a(x-b)+a(a-b)} {a(b-a)+a(a-b)}. $$

Proof. The potential-kernel equation shows that $x\mapsto a(x-a)-a(x-b)$ is harmonic except at $a$ and $b$: its one-step change is $\mathbf 1_{\{x=a\}}-\mathbf 1_{\{x=b\}}$. Adding the constant $a(a-b)$ preserves harmonicity. The resulting function $$ H(x)=a(x-a)-a(x-b)+a(a-b) $$ satisfies $H(a)=0$ and $H(b)=D$. Its values are bounded in $x$ by the fixed-difference estimate established above.

Also, $D>0$. Indeed, using the Fourier representation for the sum of the two kernel values gives $$ D=\frac{1}{2\pi}\int_{-\pi}^{\pi} 2(1-\cos(dt))\, \operatorname{Re}\!\left(\frac{1}{1-\phi(t)}\right)\,dt, \qquad d=b-a\ne0, $$ with the integral interpreted by its finite symmetric limit at zero. The real part is $(1-\operatorname{Re}\phi(t))/|1-\phi(t)|^2\ge0$, and the integrand is strictly positive on a set of positive measure by irreducibility. Hence $D>0$.

Now $H(x+S_{n\wedge T})/D$, with $T=T_a\wedge T_b$, is a bounded martingale: before $T$, the function is harmonic, and after $T$, the stopped value is constant. Bounded convergence and $T<\infty$ almost surely give $$ \frac{H(x)}{D} =\mathbb E_x\!\left[\frac{H(x+S_T)}{D}\right] =\mathbb P_x(T_b<T_a), $$ because the terminal value is $0$ at $a$ and $1$ at $b$. This proves the formula. $\square$

The formula concerns which of the two sites is visited first, not which side of an interval is exited first. For walks with jumps larger than one, the walk can overshoot an interval without visiting its endpoint. The harmonic function above avoids assuming that the path moves in unit steps.

Worked Example: Hitting One Endpoint Before the Other

For the symmetric simple walk, $a(y)=|y|$. Take target sites $0$ and $4$, starting from $1$. The denominator is $a(4)+a(-4)=4+4=8$. The numerator for hitting $4$ first is $$ a(1)-a(-3)+a(-4)=1-3+4=2. $$ Therefore $\mathbb P_1(T_4<T_0)=2/8=1/4$. This agrees with the linear hitting probability on the interval, but the potential-kernel formula applies more generally to recurrent walks that may jump over sites.

Interpretation and a Common Pitfall

The potential kernel is a renormalized Green function: it compares occupation near the origin with occupation near a displaced site, then removes the common divergence through an Abel limit. Its equation records the resulting source at the origin, while differences of translates cancel that source everywhere except at the two target sites. Normalizing those boundary values produces the hitting probability.

A common error is to reverse the sign in the Abel telescoping correction. The exact correction is negative, as shown in the proof. It vanishes in the limit, so the final kernel equation is unchanged, but the finite-$r$ identity is useful for checking the derivation. Another error is to assume that a walk must pass through every point between two targets. That is true for nearest-neighbor walks, not for general integer-valued walks; the two-target formula itself needs no such assumption.

Check Your Understanding

Try to answer each question from the definitions and arguments above.

Why is an Abel factor used in defining the potential kernel for a recurrent walk?
What is the sign of the correction term in the finite-$r$ potential-kernel equation, and why does it vanish as $r\uparrow1$?
Where is the potential kernel harmonic, and what is the value of its one-step increment at the origin?
Why does the two-target hitting formula not require a nearest-neighbor assumption?
For the lazy symmetric walk with $q=1/4$, what are $a(2)$ and the variance?