Capacity and Escape Probability

Escape from a Finite Set

For a transient random walk, a finite set can be visited only finitely many times almost surely. The probability of never returning to that set therefore records how readily the walk escapes it. Capacity packages these escape probabilities into a single number.

The definition is local: at each point of the set, measure the chance of avoiding the set after time zero. The resulting function is the equilibrium measure; its total mass is the capacity. Green functions give a useful way to compute this measure, especially when the set has several points.

Definitions

Let $(X_n)_{n\geq 0}$ be a transient Markov chain on a countable state space $S$, with transition probabilities $P(x,y)$. Write $P_x$ for probability when $X_0=x$. For a set $K\subseteq S$, define the first hitting time and the first return time by

T_K=\inf\{n\geq 0:X_n\in K\}, \qquad T_K^+=\inf\{n\geq 1:X_n\in K\},

where the infimum of the empty set is $\infty$. The Green function is

G(x,y)=\sum_{n=0}^{\infty}P_x(X_n=y).

Transience means these expected visit counts are finite. For a finite set $K$, define its equilibrium measure at $y$ to be the probability of starting at $y$ and never returning to $K$, when $y\in K$. Set the measure to zero outside $K$.

Definition: For finite $K\subseteq S$, its equilibrium measure $e_K:S\to[0,1]$ and capacity are $$ e_K(y)=\mathbf{1}_{\{y\in K\}}P_y(T_K^+=\infty), \qquad \operatorname{cap}(K)=\sum_{y\in K}e_K(y). $$ For $K=\varnothing$, set $\operatorname{cap}(K)=0$.

The indicator ensures that $e_K$ vanishes off $K$. Capacity is nonnegative and finite because $K$ is finite. For a nonempty finite set in an irreducible transient chain, it is also positive: if every point had zero probability of escaping forever, a walk starting in $K$ would return to $K$ infinitely often almost surely, contradicting transience.

Green Functions and Equilibrium Measure

The equilibrium measure has a potential-theoretic characterization: its Green potential is exactly the probability of ever hitting $K$. The proof uses the fact that, on a path which hits $K$, there is almost surely a last visit to $K$. Transience guarantees this last visit exists: the expected total number of visits to a finite $K$ is $\sum_{y\in K}G(x,y)<\infty$, so the number of such visits is finite almost surely.

Theorem: For every finite $K\subseteq S$ and every $x\in S$, $$ P_x(T_K<\infty)=\sum_{y\in K}G(x,y)e_K(y). $$ In particular, for $x\in K$, the right-hand side equals $1$.

Proof. For each $n\geq 0$ and $y\in K$, consider the event that $X_n=y$ and that $X_m\notin K$ for every $m>n$. These events are disjoint over all pairs $(n,y)$. Their union agrees, up to a probability-zero event, with $\{T_K<\infty\}$: a path that hits $K$ has a last visit to $K$, and at that time its state is some $y\in K$. By the Markov property, the probability of the event indexed by $(n,y)$ is $P_x(X_n=y)e_K(y)$. Summing over $n$ and $y$ gives $$ P_x(T_K<\infty) =\sum_{y\in K}\sum_{n=0}^{\infty}P_x(X_n=y)e_K(y) =\sum_{y\in K}G(x,y)e_K(y). $$ If $x\in K$, then $T_K=0$, so $P_x(T_K<\infty)=1$. $\square$

Thus, when the starting point $x$ ranges over $K$, the equilibrium measure satisfies a finite system of equations:

\sum_{y\in K}G(x,y)e_K(y)=1, \qquad x\in K.

This is a practical computational tool. For a finite subset of a lattice, one forms the matrix of Green-function values between its points and solves for the equilibrium masses. The probabilities themselves determine which solution is relevant; in symmetric examples, symmetry often reduces the number of unknowns.

Worked Examples

Worked Example: A Singleton for a Transient Walk

Let $K=\{a\}$ in any transient Markov chain. Starting from $a$, the probability of never returning to $a$ is $e_K(a)$. Apply the Green-function identity with $x=a$. Since $a\in K$, the probability of hitting $K$ is $1$, and the sum has just one term:

$$ 1=G(a,a)e_K(a). $$

Transience gives $G(a,a)<\infty$, while $G(a,a)\geq 1$ because the term $n=0$ contributes $1$. Hence

e_K(a)=\frac{1}{G(a,a)}, \qquad \operatorname{cap}(\{a\})=\frac{1}{G(a,a)}.

The identity also checks directly against the definition: the expected number of visits to $a$, including the initial visit, is $G(a,a)$, and the escape probability is its reciprocal.

Worked Example: An Interval for a Right-Drifting Walk

Consider the nearest-neighbor walk on $\mathbb{Z}$ that moves one step right with probability $p$ and one step left with probability $q=1-p$, where $p>q$. It is transient to the right. Let $K=\{a,a+1,\ldots,b\}$, where $a<b$.

For $x\in\{a+1,\ldots,b-1\}$, both possible next states lie in $K$, so $e_K(x)=0$. At $a$, a left step goes to $a-1$, but from $a-1$ the walk hits $a$ almost surely: by the strong law, the walk tends to $+\infty$, and its nearest-neighbor path must cross $a$. A right step stays in $K$. Thus $e_K(a)=0$ as well.

At $b$, a left step stays in $K$. A right step moves to $b+1$, from which the probability of ever hitting $b$ is $q/p$. To see this, the hitting probability $h_k=P_{b+k}(T_{\{b\}}<\infty)$, for $k\geq0$, satisfies $h_0=1$ and

h_k=p h_{k+1}+q h_{k-1}\quad (k\geq1).

The bounded solution tending to zero as $k\to\infty$ is $h_k=(q/p)^k$, which satisfies the recurrence since $p(q/p)^{k+1}+q(q/p)^{k-1}=(q/p)^k$. Therefore the chance of never returning from $b+1$ is $1-q/p$, and

e_K(b)=p\left(1-\frac{q}{p}\right)=p-q.

All other equilibrium masses are zero, so summing them gives

\operatorname{cap}(K)=p-q.

In particular, the capacity does not depend on the interval's length. The reason is that a path leaving through the left endpoint returns to the interval almost surely; escape is possible only by moving right from its right endpoint.

Worked Example: Two Points in a Transient Lattice

Let $(X_n)$ be simple symmetric random walk on $\mathbb{Z}^d$, with $d\geq3$, and take $K=\{0,z\}$, where $z\neq0$. Write $g(w)=G(0,w)$. Translation invariance and symmetry give $G(0,0)=G(z,z)=g(0)$ and $G(0,z)=G(z,0)=g(z)$. Reflection and translation symmetry also imply $e_K(0)=e_K(z)=c$. The Green equations at $0$ and $z$ are both

\bigl(g(0)+g(z)\bigr)c=1.

Since $g(0)$ is finite by transience and $g(z)\geq0$, the coefficient is positive. Thus $c=1/(g(0)+g(z))$, and

\operatorname{cap}(\{0,z\}) =\frac{2}{g(0)+g(z)}.

Substitution verifies the equations: the potential at either point is $g(0)c+g(z)c=1$. The formula shows how the interaction between the two points enters through $g(z)$; treating the points as independent singletons would omit this term.

Computing Capacity for a General Finite Lattice Set

For a finite set $K=\{x_1,\ldots,x_m\}$ in a transient lattice walk, define the Green matrix $M$ by $M_{ij}=G(x_i,x_j)$. If $e_j=e_K(x_j)$, the equations on $K$ become

\sum_{j=1}^{m}M_{ij}e_j=1, \qquad i=1,\ldots,m, \qquad \operatorname{cap}(K)=\sum_{j=1}^{m}e_j.

This is a finite linear system, but it should be used with care. The desired solution is the vector of escape probabilities from the definition. In particular, the entries must be nonnegative. A proposed vector can be checked by substituting it into every row of the Green system, then summing its entries to obtain the capacity. For symmetric walks, $M$ is symmetric, which often makes the system especially tractable.

A useful consistency check is monotonicity: if $A\subseteq B$, then $P_x(T_A<\infty)\leq P_x(T_B<\infty)$ for every $x$, since hitting $A$ implies hitting $B$. Capacity itself is not obtained by summing these hitting probabilities over starting points; it is the sum of the equilibrium masses on the set. The Green identity explains how those masses generate the hitting probabilities.

Why Capacity Matters

Capacity gives a scalar summary of a finite set's ability to be escaped from in a transient environment. A small escape probability at every point produces a small total mass; a set with accessible routes to infinity can have larger capacity. The Green equations make this interpretation quantitative: equilibrium mass at $y$ contributes $G(x,y)e_K(y)$ to the probability of ever reaching the set from $x$.

A common pitfall is to confuse escape probability from one point with capacity. For a singleton they are equal, but for a larger set capacity is the sum of the pointwise escape probabilities, not the escape probability from an arbitrarily chosen starting point. Another pitfall is to assign positive equilibrium mass to every point automatically. In the biased interval example, all mass lies at the right endpoint; at the left endpoint, stepping out does not create a genuine escape because return occurs almost surely.

Check Your Understanding

Use the definitions and Green identity to answer the following questions.

Why is the equilibrium measure zero outside the finite set $K$?
How does transience ensure that a path which hits $K$ has a last visit to $K$ almost surely?
For a singleton $\{a\}$, how is capacity related to $G(a,a)$?
For the right-drifting walk and interval $\{a,\ldots,b\}$, why is the equilibrium mass at $a$ zero even though a step from $a$ can leave the interval?
What finite system must the equilibrium masses of a finite lattice set satisfy?