Killed Green Functions and Boundary Flux

Why killed Green functions are useful

A walk observed only until it leaves a region has two linked features: how often it visits each interior state, and where it eventually exits. The killed Green function records the first feature. Its transition equations then show how expected visits generate the second: probability flows from each interior state across the boundary in proportion to how often the walk visits that state.

We work with a Markov chain on a measurable state space $S$, with transition kernel $P(x,B)$. Thus, for a state $x$ and a measurable set $B\subseteq S$, $P(x,B)$ is the conditional probability that the next state lies in $B$, given that the current state is $x$. In particular, $P(x,\{y\})$ is meaningful when singletons are measurable. We take the domain $D\subseteq S$ to be finite, so its points are measurable, and write $D^c=S\setminus D$.

Exit time and killed Green function

Definition: For a chain $(X_n)_{n\geq 0}$ started at $x\in D$, its exit time from $D$ is the first time it is outside $D$: $$ \tau_D=\inf\{n\geq 0:X_n\notin D\}. $$ The killed Green function $G_D(x,y)$, for $x,y\in D$, is the expected number of visits to $y$ before exit: $$ G_D(x,y)=\mathbb{E}_x\!\left[\sum_{n=0}^{\tau_D-1}\mathbf{1}_{\{X_n=y\}}\right] =\sum_{n=0}^{\infty}\mathbb{P}_x(X_n=y,\ n<\tau_D). $$

The sum stops before the exit step: $X_{\tau_D}$ is outside $D$, and is not counted as an interior visit. The second expression also makes sense if the expected number of visits is infinite. For the finite-matrix equations and numerical examples below, we assume $\mathbb{E}_x[\tau_D]<\infty$ for every $x\in D$. Under this assumption the Green function is finite, and exit occurs almost surely.

Write $Q$ for the matrix of transitions that stay inside $D$, with entries $Q(x,y)=P(x,\{y\})$, for $x,y\in D$. By the Markov property, $(Q^n)(x,y)=\mathbb{P}_x(X_n=y,\ n<\tau_D)$. Consequently, the Green matrix is the sum of these powers.

G_D=\sum_{n=0}^{\infty}Q^n.

Worked Example: A two-state domain with two exit sets

Let $D=\{a,b\}$. From $a$, the chain moves to $b$ with probability $0.4$ and exits into a measurable set $A$ with probability $0.6$. From $b$, it moves to $a$ with probability $0.2$, exits into a disjoint measurable set $B$ with probability $0.3$, and stays at $b$ with probability $0.5$. These probabilities sum to $1$ at both states. The interior transition matrix is

Q=\begin{pmatrix}0&0.4\\0.2&0.5\end{pmatrix}, \qquad I-Q=\begin{pmatrix}1&-0.4\\-0.2&0.5\end{pmatrix}.

The determinant of $I-Q$ is $0.5-0.08=0.42$, so $$ G_D=(I-Q)^{-1} =\frac{1}{0.42}\begin{pmatrix}0.5&0.4\\0.2&1\end{pmatrix} =\begin{pmatrix}25/21&20/21\\10/21&50/21\end{pmatrix}. $$ For example, starting at $a$, the expected number of visits to $a$ before exit is $25/21$, and the expected number of visits to $b$ is $20/21$. The probabilities of exiting into $A$ from $a$ or $b$ are respectively $$ \frac{25}{21}(0.6)=\frac57, \qquad \frac{10}{21}(0.6)=\frac27. $$ The corresponding probabilities of exiting into $B$ are $$ \frac{20}{21}(0.3)=\frac27, \qquad \frac{50}{21}(0.3)=\frac57. $$ From either starting state, the probabilities of exiting into $A$ and $B$ add to $1$. In this example the chain has no other exit destinations, so the check also confirms that exit occurs with total probability $1$.

Transition equations for occupation

The Green function satisfies a first-step equation. Starting from $x$, there is one visit to $y$ at time $0$ if $x=y$. If the first step stays in $D$, the expected subsequent visits are given by the Green function from the new state. If the first step exits, it contributes no later visit to any state in $D$.

Theorem: If $D$ is finite and $\mathbb{E}_x[\tau_D]<\infty$ for every $x\in D$, then for all $x,y\in D$, $$ G_D(x,y)=\mathbf{1}_{\{x=y\}}+\sum_{z\in D}P(x,\{z\})G_D(z,y). $$ Equivalently, $G_D=I+QG_D$, and hence $(I-Q)G_D=I$.

Proof. Split the visits to $y$ before exit into the possible visit at time $0$ and visits at times $n\geq 1$. The time-zero contribution is $\mathbf{1}_{\{x=y\}}$. For each $z\in D$, conditional on $X_1=z$, the chain from time $1$ onward has the law of a chain started at $z$, and the expected number of subsequent visits to $y$ before exit is $G_D(z,y)$. If $X_1\notin D$, the number of subsequent visits to $y$ before exit is zero. Taking expectations over the first step gives $$ G_D(x,y)=\mathbf{1}_{\{x=y\}}+\sum_{z\in D}P(x,\{z\})G_D(z,y). $$ The sum is finite because $D$ is finite. In matrix form this is $G_D=I+QG_D$, which rearranges to $(I-Q)G_D=I$. $\square$

The power-series form gives the same identity directly: multiplying the partial sum $I+Q+\cdots+Q^N$ by $I-Q$ leaves $I-Q^{N+1}$. The finite expected exit assumption implies $Q^{N+1}$ tends entrywise to zero: its row sums are probabilities of remaining in $D$ for $N+1$ steps, and those probabilities tend to zero. Thus the limit is $G_D$ and $G_D=(I-Q)^{-1}$.

Boundary flux as an exit distribution

For a measurable set $A\subseteq D^c$, define $P(y,A)$ to be the one-step transition probability from $y$ into $A$. This is a kernel value, not necessarily a sum of point probabilities. The event of exiting into $A$ can occur at any step $n+1$: the chain must first be at some $y\in D$ at time $n$, then its next transition must land in $A$.

Theorem: If $D$ is finite and $\mathbb{E}_x[\tau_D]<\infty$ for every $x\in D$, then for $x\in D$ and every measurable $A\subseteq D^c$, $$ \mathbb{P}_x(X_{\tau_D}\in A) =\sum_{y\in D}G_D(x,y)P(y,A). $$

Proof. For each $n\geq0$, the event that the walk exits into $A$ at time $n+1$ is $\{n<\tau_D,\ X_{n+1}\in A\}$. These events are disjoint as $n$ varies, and, because exit occurs almost surely, their union is $\{X_{\tau_D}\in A\}$. Conditioning on $X_n$ and using the Markov property gives $$ \begin{aligned} \mathbb{P}_x(X_{\tau_D}\in A) &=\sum_{n=0}^{\infty}\sum_{y\in D} \mathbb{P}_x(X_n=y,\ n<\tau_D)\,P(y,A)\\ &=\sum_{y\in D} \left(\sum_{n=0}^{\infty}\mathbb{P}_x(X_n=y,\ n<\tau_D)\right)P(y,A)\\ &=\sum_{y\in D}G_D(x,y)P(y,A). \end{aligned} $$ The rearrangement is valid because all terms are nonnegative; also, the sum over $D$ is finite. This identifies the exit probability as the total expected flux into $A$ from all interior states. $\square$

There is a matching transition equation for the exit probability $h_A(x)=\mathbb{P}_x(X_{\tau_D}\in A)$. Conditioning on the first step gives $$ h_A(x)=P(x,A)+\sum_{z\in D}P(x,\{z\})h_A(z). $$ The first term accounts for an immediate exit into $A$; the sum accounts for a first step to another interior state. In matrix notation, $h_A=r_A+Qh_A$, where $r_A(x)=P(x,A)$. Since $G_D=(I-Q)^{-1}$, the equation has the solution $h_A=G_Dr_A$, precisely the boundary-flux formula.

Worked Example: Simple random walk on a finite interval

Consider the symmetric simple random walk on the integers, killed when it leaves $D=\{1,2,3\}$. From state $1$ it moves to $0$ or $2$ with probability $1/2$ each; from $2$ it moves to $1$ or $3$; and from $3$ it moves to $2$ or $4$. The exit points are $0$ and $4$. The interior matrix is $$ Q=\begin{pmatrix}0&1/2&0\\1/2&0&1/2\\0&1/2&0\end{pmatrix}. $$ A direct inverse gives $$ G_D=(I-Q)^{-1} =\begin{pmatrix}3/2&1&1/2\\1&2&1\\1/2&1&3/2\end{pmatrix}. $$ For verification, multiplying the first row of $I-Q$, namely $(1,-1/2,0)$, by the columns of this proposed inverse gives $3/2-1/2=1$, $1-1=0$, and $1/2-1/2=0$. The second row $(-1/2,1,-1/2)$ gives $ -3/4+1-1/4=0$, $-1/2+2-1/2=1$, and $-1/4+1-3/4=0$. The third row gives $0,0,1$ by the same calculation. Thus the product is the identity.

From $x=2$, the expected visits to $1$ and $3$ are both $1$. The only transition into $0$ is from $1$, with probability $1/2$, and the only transition into $4$ is from $3$, also with probability $1/2$. Therefore $$ \mathbb{P}_2(X_{\tau_D}=0)=G_D(2,1)\frac12=\frac12, \qquad \mathbb{P}_2(X_{\tau_D}=4)=G_D(2,3)\frac12=\frac12. $$ From $x=1$, the two probabilities are $G_D(1,1)/2=3/4$ and $G_D(1,3)/2=1/4$. They sum to $1$ in each case, as required because the walk exits this finite interval almost surely.

Worked Example: A noncountable exit space

Let the state space consist of one interior state $y$ and the interval $[0,1]$, with the usual measurable sets on the interval. Take $D=\{y\}$. From $y$, let the next state have the uniform distribution on $[0,1]$. Once the chain is at a point $z\in[0,1]$, let it stay at $z$. Then $\tau_D=1$ when the chain starts at $y$, and $$ G_D(y,y)=1,\qquad P(y,A)=\operatorname{Leb}(A) $$ for every measurable $A\subseteq[0,1]$, where $\operatorname{Leb}$ denotes interval length. The boundary-flux formula yields $$ \mathbb{P}_y(X_{\tau_D}\in A)=G_D(y,y)P(y,A)=\operatorname{Leb}(A). $$ In particular, for each single point $z\in[0,1]$, $P(y,\{z\})=0$, while $P(y,[0,1])=1$. This is why exit probabilities for general state spaces must use transition probabilities to measurable sets, rather than an assumed sum over individual boundary states.

Interpretation and a common pitfall

The boundary-flux identity has a useful interpretation: $G_D(x,y)$ is the expected number of opportunities to leave $D$ from $y$, while $P(y,A)$ is the probability that any one such opportunity lands in $A$. Summing their products over interior states gives the probability of exit into $A$. The identity is not an approximation; it follows by partitioning according to the step on which exit occurs.

A common pitfall is to replace $P(y,A)$ with $\sum_{z\in A}P(y,\{z\})$ without assuming a countable state space. For a noncountable boundary, that sum may fail to represent the probability of the set, as the uniform example shows. Another point to keep clear is the finiteness assumption used for the matrix inverse: if the chain can remain in $D$ forever with positive probability, the exit distribution may have total mass less than $1$, and Green entries may be infinite. The kernel-based step-by-step flux argument still explains the exit events, but the finite inverse formula requires the stated finite expected exit condition.

Check Your Understanding

Use the definitions and equations above to answer the following.

Why does the definition of $G_D(x,y)$ count visits only up to time $\tau_D-1$, rather than counting $X_{\tau_D}$?
Write the first-step equation for $G_D(x,y)$, and identify the contribution from a transition that exits $D$.
For a measurable $A\subseteq D^c$, what does $P(y,A)$ represent in the boundary-flux formula?
In the interval example, calculate the probability of exiting at $0$ when the walk starts at $3$.
Why is a sum of point probabilities not a valid general replacement for $P(y,A)$ on a noncountable state space?

Killed Green Functions and Boundary Flux

What You'll Learn

Why killed Green functions are useful

Exit time and killed Green function

Worked Example: A two-state domain with two exit sets

Worked Example: A two-state domain with two exit sets

Transition equations for occupation

Boundary flux as an exit distribution

Worked Example: Simple random walk on a finite interval

Worked Example: Simple random walk on a finite interval

Worked Example: A noncountable exit space

Worked Example: A noncountable exit space

Interpretation and a common pitfall

Check Your Understanding

Previous

Next