Last-Exit Decomposition for Random Walks

Why Count Visits Before the Last Exit?

A transient walk can visit a finite set several times before it finally leaves and never returns. The Green function counts all visits, so by itself it does not give the probability of hitting the set: a trajectory that visits repeatedly contributes more than once. The last-exit decomposition corrects for this by weighting each visit according to the probability that it is the final visit.

The resulting identity is useful because it separates two quantities with different roles: the expected number of visits to each point, and the probability that a visit there ends with a departure from which the walk never returns to the set. It also identifies the destination of that final departure.

Setup and Definitions

Let $(X_n)_{n\in\mathbb N_0}$ be a Markov chain on a countable state space $S$, with transition probabilities $P(x,y)=\mathbb P_x(X_1=y)$. Write $\mathbb P_x$ and $\mathbb E_x$ for probability and expectation when $X_0=x$. Assume the chain is transient, meaning that its Green function is finite for every pair $x,y\in S$:

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

For a finite set $A\subseteq S$, define its hitting time by $T_A=\inf\{n\in\mathbb N_0:X_n\in A\}$, with the infimum of the empty set taken to be $+\infty$. Starting from $z\in A$, the walk has made a visit to $A$ at time zero. The probability that it makes no further visit is the terminal-visit probability.

Definition: For $z\in A$, define $$ e_A(z)=\mathbb P_z(X_n\notin A\text{ for every }n\ge 1). $$ For $w\in A^c$, define the terminal exit measure $$ e_A(z,w)=\mathbb P_z(X_1=w,\ X_n\notin A\text{ for every }n\ge 1). $$ Thus $e_A(z)=\sum_{w\in A^c}e_A(z,w)$. The event counted by $e_A(z,w)$ is that the step from $z$ to $w$ is followed by no return to $A$.

This is not the usual distribution of the first step on leaving $A$. A first exit may be followed by a return and further visits. The terminal exit measure counts only departures that are never followed by another visit.

The Last-Exit Decomposition

Transience ensures that a finite set is visited only finitely many times almost surely. Indeed, the expected number of visits to $A$ from $x$ is

\mathbb E_x\!\left[\sum_{n=0}^{\infty}\mathbf 1_{\{X_n\in A\}}\right] =\sum_{z\in A}G(x,z)<\infty.

A nonnegative integer-valued count that is infinite with positive probability has infinite expectation. Hence the visit count is finite almost surely, and, if the walk ever visits $A$, there is a well-defined last time it does so.

Theorem (last-exit decomposition): For every finite $A\subseteq S$ and every $x\in S$, $$ \mathbb P_x(T_A<\infty) =\sum_{z\in A}G(x,z)e_A(z) =\sum_{z\in A}\sum_{w\in A^c}G(x,z)e_A(z,w). $$ Moreover, the probability that the final step out of $A$ is from $z$ to $w$ is $G(x,z)e_A(z,w)$.

Proof. For $n\in\mathbb N_0$ and $z\in A$, let $E_{n,z}$ be the event that $X_n=z$ and $X_m\notin A$ for every $m>n$. These events are pairwise disjoint: if a path is in $E_{n,z}$, it has no visit to $A$ after time $n$, so it cannot also be in $E_{k,u}$ for $k>n$. Their union is exactly the event that the walk visits $A$: every such path has a last visit, and that visit has some time $n$ and state $z\in A$. By the Markov property at deterministic time $n$, $$ \mathbb P_x(E_{n,z}) =\mathbb P_x(X_n=z)\mathbb P_z(X_m\notin A\text{ for every }m\ge1) =\mathbb P_x(X_n=z)e_A(z). $$ Summing over the disjoint events and then over $n$ gives $$ \mathbb P_x(T_A<\infty) =\sum_{z\in A}\sum_{n=0}^{\infty}\mathbb P_x(X_n=z)e_A(z) =\sum_{z\in A}G(x,z)e_A(z). $$ For a final exit to $w$, replace the event of no further visit by the event that the first step after time $n$ is to $w$ and there are no later visits. The same disjoint-event argument gives probability $\sum_{z\in A}G(x,z)e_A(z,w)$ for that exit destination. Finally, summing over $w\in A^c$ gives the stated formula because $e_A(z)=\sum_{w\in A^c}e_A(z,w)$. All sums have nonnegative terms, so this rearrangement is valid. $\square$

The factor $G(x,z)$ counts the expected number of visits to $z$, including a visit at time zero when $x=z$. Each such visit has probability $e_A(z)$ of being the final visit to $A$. The identity therefore adds the probabilities of all possible last visits, not the probabilities of all visits.

Worked Examples

Worked Example: A Deterministic Transient Chain

Let $S=\mathbb N_0$ and let the chain move deterministically from $i$ to $i+1$. Take $A=\{2,4\}$ and start from $x=0$. Each state is visited at most once, so $G(0,2)=G(0,4)=1$. Starting at 2, the chain next reaches 4, so it does return to $A$ after time zero and $e_A(2)=0$. Starting at 4, it moves to 5 and never returns, so $e_A(4)=1$. Therefore

\mathbb P_0(T_A<\infty) =G(0,2)e_A(2)+G(0,4)e_A(4) =1\cdot0+1\cdot1=1.

The last visit is always at 4, and the terminal exit destination is 5. In particular, counting the visit to 2 as well as the visit to 4 without the terminal-visit weights would give 2, not a hitting probability.

Worked Example: Hitting One Point in a Biased 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$. Let $A=\{0\}$. The probability of returning to 0 after time zero is $2q$: a first step left returns to 0 with probability 1, while a first step right returns with probability $q/p$. Thus

e_{\{0\}}(0)=1-2q=p-q.

The Green function at 0 is the expected number of visits to 0 starting there. Each return after time zero has probability $2q$, so the number of visits, including the initial one, has mean $1+2q+(2q)^2+\cdots=1/(p-q)$. For $x>0$, the probability of ever hitting 0 is $(q/p)^x$; for $x\le 0$, it is 1. By the Markov property at the first hit of 0, the expected number of visits to 0 is that hitting probability times $G(0,0)$. Consequently, $$ G(x,0)= \begin{cases} \dfrac{1}{p-q},&x\le0,\\[4pt] \dfrac{(q/p)^x}{p-q},&x>0. \end{cases} $$ The last-exit formula gives $$ \mathbb P_x(T_{\{0\}}<\infty)=G(x,0)(p-q) = \begin{cases} 1,&x\le0,\\ (q/p)^x,&x>0. \end{cases} $$ For example, from $x=2$, the product is $(q/p)^2$, the probability of reaching 0 against the drift. The formula recovers the hitting probability from an expected visit count and the chance of no return after a visit.

Worked Example: A Two-Point Set in the Biased Walk

Use the same walk, now with $A=\{0,1\}$. From 0, a step to the right lands in $A$, while a step to the left reaches $-1$, from which the walk returns to 0 with probability 1. Thus $e_A(0)=0$. From 1, a step left lands in $A$, while a step right reaches 2. Starting from 2, the probability of ever hitting 1 is $q/p$, so the probability of never returning to $A$ after that rightward step is $1-q/p$. It follows that

e_A(1)=p\left(1-\frac qp\right)=p-q.

For $x\ge2$, the walk must hit 1 before it can hit 0, and its probability of doing so is $(q/p)^{x-1}$. After the first hit of 1, its expected number of visits to 1 is $G(1,1)=1/(p-q)$. Therefore $G(x,1)=(q/p)^{x-1}/(p-q)$, and the decomposition yields

\mathbb P_x(T_A<\infty) =G(x,0)e_A(0)+G(x,1)e_A(1) =\left(\frac qp\right)^{x-1}.

For $x=2$, this is $q/p$, as required: reaching either 0 or 1 from 2 first requires hitting 1. For $x=1$, $G(1,1)=1/(p-q)$, so the formula gives 1, as it must. Although $A$ has two points, only 1 can be the final visit state: a visit to 0 is always followed by another visit to $A$.

What the Exit-Destination Formula Adds

The refined version records more than whether $A$ is hit. For a fixed $w\in A^c$, the quantity

\sum_{z\in A}G(x,z)e_A(z,w)

is the probability that the final transition out of $A$ lands at $w$. Summing this over all $w\in A^c$ recovers the probability of hitting $A$. This can be useful when the destination of the final departure matters, for example when comparing the ways a walk escapes a finite region.

A common pitfall is to replace $e_A(z)$ by the probability that the next step leaves $A$. That quantity only describes an immediate exit; it does not rule out a later return. In the two-point example, a step from 1 to 2 leaves $A$, but it is terminal only if the walk never comes back. The factor $1-q/p$, not 1, is therefore essential.

Check Your Understanding

Use the definitions and decomposition to answer the following questions.

Why does transience imply that a finite set is visited only finitely many times almost surely?
In the last-exit formula, what does $G(x,z)$ count, and what does $e_A(z)$ measure?
Why are the events specifying the last visit at times $n$ and $k$, with $n\ne k$, disjoint?
What is the difference between an ordinary first exit from $A$ and a terminal exit?
For the biased walk with $p>q$ and $A=\{0,1\}$, why is $e_A(0)=0$ but $e_A(1)=p-q$?