Why Green Functions Have Recursions
A Green function records how often a Markov chain visits a state, on average. Its definition sums contributions over all times, but the Markov property gives another way to organize that sum: separate the visit at time zero from visits after the first transition. This yields a first-step equation.
There is an important qualification. An undiscounted expected visit count can be infinite, so its equations may be equations of extended nonnegative quantities rather than ordinary finite matrix identities. Discounting by a factor \(r^n\), with \(0<r<1\), avoids this difficulty at the operator level: the resulting series always converges on bounded functions.
Green Kernels and Transition Operators
Let \(S\) be a finite or countable state space, and let \(P=(p(x,y))_{x,y\in S}\) be a transition matrix: \(p(x,y)\geq 0\) and \(\sum_{y\in S}p(x,y)=1\) for every \(x\). Write \(P^0(x,y)=\mathbf{1}_{\{x=y\}}\), and let \(P^n(x,y)\) be the \(n\)-step transition probability. The same definitions apply to a substochastic transition matrix, whose row sums are at most one, when probability lost from \(S\) represents killing.
For a function \(f:S\to\mathbb{R}\), the transition operator is \(Pf(x)=\sum_y p(x,y)f(y)\), whenever the sum is defined. In particular, if \(f\) is bounded, then \(Pf\) is defined and bounded, and \(\|Pf\|_\infty\leq\|f\|_\infty\). Here \(\|f\|_\infty=\sup_{x\in S}|f(x)|\). The discounted Green operator is the operator series \(R_r=\sum_{n=0}^{\infty}r^nP^n\), acting on bounded functions.
Thus the discounted series converges in operator norm on bounded functions. Its kernel is \(G_r\): for bounded \(f\), \(R_rf(x)=\sum_y G_r(x,y)f(y)\). The nonnegative sums can be interchanged by Tonelli’s theorem; for signed bounded \(f\), absolute convergence follows from the displayed bound.
The First-Step and Last-Step Equations
At time zero, the chain is at its initial state. Every later transition probability can be decomposed according to the state occupied after the first step. This gives the first-step equation. One can also decompose according to the state immediately before the final step, giving a corresponding last-step equation.
Proof. For each \(n\geq 0\), the Chapman–Kolmogorov equations give \(P^{n+1}(x,y)=\sum_z p(x,z)P^n(z,y)\). Summing over \(n\geq0\), and using Tonelli’s theorem to interchange nonnegative sums, yields \(\sum_{n\geq1}P^n(x,y)=\sum_z p(x,z)\sum_{n\geq0}P^n(z,y)\). Adding \(P^0(x,y)=\mathbf{1}_{\{x=y\}}\) proves the first Green equation. The other decomposition, \(P^{n+1}(x,y)=\sum_z P^n(x,z)p(z,y)\), gives the last-step equation by the same nonnegative summation. Multiplying the terms of the two sums by \(r^n\) gives the discounted equations: the term with \(n+1\) contributes a factor \(r\), leaving the discounted sum over \(n\geq0\). All these manipulations are valid for nonnegative series, including when an undiscounted sum is infinite. \(\square\)
In particular, if every entry of \(G\) is finite, the first equation is written in matrix notation as \(G=I+PG\), and the second as \(G=I+GP\), with sums over \(S\) understood. These identities do not imply that an inverse \( (I-P)^{-1}\) exists: \(G\) need not be a bounded operator, or even have finite entries. The discounted case has a stronger operator statement.
The Discounted Resolvent Identity
Proof. Since \(P\) is a contraction, \(\|r^nP^n\|\leq r^n\). The geometric series \(\sum_n r^n\) is finite, so the operator series converges in operator norm. For its partial sum \(R_{r,N}=\sum_{n=0}^{N}r^nP^n\), multiplication and cancellation of consecutive terms give \((I-rP)R_{r,N}=R_{r,N}(I-rP)=I-r^{N+1}P^{N+1}\). The remainder has norm at most \(r^{N+1}\), which tends to zero as \(N\) tends to infinity. Passing to the operator-norm limit proves both identities.
This is the resolvent identity in its series form. At the kernel level, the two operator products correspond to the discounted first-step and last-step equations. For bounded \(f\), the operator identities justify applying \(I-rP\) on either side of the convergent series; no assumption that the undiscounted Green operator exists as a bounded operator is needed.
Worked Example: A Finite Killed Chain
Worked Example: A Finite Killed Chain
Consider the substochastic transition matrix on \(S=\{a,b\}\) \(Q=\begin{pmatrix}1/2&1/2\\0&0\end{pmatrix}\). From \(a\), the chain remains at \(a\) with probability \(1/2\), moves to \(b\) with probability \(1/2\), and from \(b\) it is killed at the next step. For \(n\geq1\), \(Q^n=\begin{pmatrix}2^{-n}&2^{-n}\\0&0\end{pmatrix}\). Indeed, multiplying this expression by \(Q\) gives \(\begin{pmatrix}2^{-(n+1)}&2^{-(n+1)}\\0&0\end{pmatrix}\), which verifies the induction step; the expression for \(n=1\) is \(Q\) itself.
Summing the powers, including \(Q^0=I\), gives \(G=\begin{pmatrix}1+\sum_{n\geq1}2^{-n}&\sum_{n\geq1}2^{-n}\\0&1\end{pmatrix} =\begin{pmatrix}2&1\\0&1\end{pmatrix}\). The first-step identity checks directly: \(QG=\begin{pmatrix}1&1\\0&0\end{pmatrix}\), so \(I+QG=\begin{pmatrix}2&1\\0&1\end{pmatrix}=G\). The entry \(G(a,b)=1\) reflects that the chain eventually reaches \(b\) with probability one and visits it once before being killed.
For discount \(0<r<1\), summing the weighted powers instead gives \(G_r=\begin{pmatrix}1+\sum_{n\geq1}(r/2)^n&\sum_{n\geq1}(r/2)^n\\0&1\end{pmatrix} =\begin{pmatrix}2/(2-r)&r/(2-r)\\0&1\end{pmatrix}\). This example has finite undiscounted entries, but the discounted formula applies without needing that finiteness.
Worked Example: A Deterministic Shift on a Countable Space
Worked Example: A Deterministic Shift on a Countable Space
Let \(S=\mathbb{N}_0\), and take \(p(i,i+1)=1\) for each \(i\). Starting from \(i\), the chain is at \(i+n\) at time \(n\). Therefore \(P^n(i,j)=1\) exactly when \(j=i+n\), and is zero otherwise. Each state \(j\geq i\) is visited exactly once, while states \(j<i\) are never visited. Consequently, \(G(i,j)=\mathbf{1}_{\{j\geq i\}}\), which is finite for every pair even though the state space is infinite.
For the first-step equation, the sum over \(z\) has only the term \(z=i+1\). Its right-hand side is \(\mathbf{1}_{\{i=j\}}+G(i+1,j)=\mathbf{1}_{\{i=j\}}+\mathbf{1}_{\{j\geq i+1\}}=\mathbf{1}_{\{j\geq i\}}=G(i,j)\). For discount \(r\), exactly one time contributes when \(j\geq i\), namely \(n=j-i\). Thus \(G_r(i,j)=r^{j-i}\) if \(j\geq i\), and \(G_r(i,j)=0\) otherwise. In particular, the discounted kernel is bounded by one entrywise, while the corresponding operator has norm at most \(1/(1-r)\).
Worked Example: Discounting an Alternating Chain
Worked Example: Discounting an Alternating Chain
On \(S=\{0,1\}\), let \(P=\begin{pmatrix}0&1\\1&0\end{pmatrix}\). The chain alternates states, so \(P^{2k}=I\) and \(P^{2k+1}=P\) for every \(k\geq0\). It visits its starting state infinitely often; hence the undiscounted diagonal Green entries are infinite. Discounting gives \(G_r=\sum_{k\geq0}r^{2k}I+\sum_{k\geq0}r^{2k+1}P =\frac{1}{1-r^2}\begin{pmatrix}1&r\\r&1\end{pmatrix}\).
The operator identity can be checked directly. Here \(I-rP=\begin{pmatrix}1&-r\\-r&1\end{pmatrix}\), and multiplying it by the displayed \(G_r\) gives \(\frac{1}{1-r^2}\begin{pmatrix}1-r^2&0\\0&1-r^2\end{pmatrix}=I\). The reverse product is also \(I\), since both matrices are symmetric and their direct multiplication gives the same entries. This illustrates why the discounted resolvent remains well-defined even when the undiscounted visit counts diverge.
What the Identities Do—and Do Not—Say
The first-step equation is often used to compute Green functions, but it is not by itself a guarantee of a finite solution. In a finite recurrent chain, a state may be visited infinitely often in expectation, and the corresponding Green entry is infinite. Writing \(G=I+PG\) as a finite matrix equation in that setting would be invalid. The safe statement is the entrywise nonnegative recursion; ordinary matrix algebra requires finiteness of the relevant sums.
Discounting supplies a reliable alternative. For every \(r<1\), the contraction bound gives a bounded operator \(R_r\), and the inverse identities hold. As \(r\) approaches one, individual entries of \(G_r\) may grow without bound. One must not simply substitute \(r=1\) into the resolvent formula or infer that \(I-P\) has an inverse. The discounted identities are exact for \(0<r<1\); conclusions at the undiscounted endpoint require separate hypotheses.
These recursions are useful because they connect expected visit counts to local transition probabilities. They allow finite-state calculations, establish kernel relations on countable spaces, and provide a controlled approximation through discounted Green functions. The distinction between a pointwise kernel identity and a bounded-operator identity is essential: the former can make sense with infinite entries, whereas the latter requires a well-defined operator on its chosen function space.
Check Your Understanding
Use the definitions and identities above to answer these questions.
- Why does the Green-kernel first-step equation include the term \(\mathbf{1}_{\{x=y\}}\)?
- Which decomposition of \(P^{n+1}(x,y)\) gives the last-step equation?
- What condition ensures that \(G=I+PG\) is an ordinary finite-valued matrix identity?
- Why does the discounted operator series converge in operator norm for \(0<r<1\)?
- For the deterministic shift, what are \(G(i,j)\) and \(G_r(i,j)\) when \(j<i\)?
- Why can the alternating chain have a well-defined discounted resolvent even though its undiscounted diagonal Green entries are infinite?