The Fundamental Matrix of an Absorbing Chain

From the Transient Block to a Matrix Series

An absorbing chain can spend several steps among transient states before it enters an absorbing state. Its transition matrix therefore contains a block $Q$ that records transitions from transient states to transient states. Repeated multiplication by $Q$ tracks paths that remain in that transient set. Adding the powers of $Q$ gives a matrix that summarizes all these successive transient transitions in one object.

Let $(X_n)_{n\ge0}$ be a discrete-time Markov chain on a finite state space $S$, defined on a probability space $(\Omega,\mathcal{F},\mathbb{P})$, with row-stochastic transition matrix $P=(p_{ij})$. Suppose the states are arranged so that the first $r$ states are transient and the remaining states are absorbing. In canonical form, write

P= \begin{bmatrix} Q&R\\ 0&I \end{bmatrix}.

Here $Q$ is the $r\times r$ transient-to-transient block, and $R$ records transitions from transient states to absorbing states. Since $P$ is row-stochastic, its entries are nonnegative, each row of $P$ sums to $1$, and each row sum of $Q$ is at most $1$. A matrix with nonnegative entries and row sums at most $1$ is called substochastic.

Definition: When the matrix series converges entrywise, the fundamental matrix of the absorbing chain is $$ N=\sum_{n=0}^{\infty}Q^n=I+Q+Q^2+Q^3+\cdots, $$ where $Q^0=I$, the identity matrix of size $r$.

The zeroth-power term is essential: the series begins with $I$, not $Q$. The term $Q^n$ is the transient block of the $n$-step transition matrix $P^n$; it records probabilities of being in transient states after $n$ steps without having left the transient block. This tutorial uses the series definition and shows how to calculate it by inversion when convergence is verified. The general existence question for finite absorbing chains is treated separately.

Why Matrix Inversion Computes the Series

For a finite matrix, a useful sufficient condition for convergence is a uniform bound on its row sums. Let $Q$ have nonnegative entries, and suppose every row sum is at most some $r_0<1$. Then the entries of $Q^n$ decay at least geometrically. This gives a direct route from the series to an inverse, without needing to compute infinitely many powers.

Proposition: If $Q$ is a finite square matrix with nonnegative entries and each row sum at most $r_0<1$, then $\sum_{n=0}^{\infty}Q^n$ converges entrywise and $$ \sum_{n=0}^{\infty}Q^n=(I-Q)^{-1}. $$

Proof. For a nonnegative matrix $A$, write $s_i(A)=\sum_j A_{ij}$ for its $i$th row sum. If $s_i(Q)\le r_0$ for every $i$, then for each $i$, $$ s_i(Q^2)=\sum_j\sum_k Q_{ik}Q_{kj} =\sum_k Q_{ik}s_k(Q) \le r_0\sum_kQ_{ik} \le r_0^2. $$ More generally, if all row sums of $Q^n$ are at most $r_0^n$, the same calculation gives $s_i(Q^{n+1})=\sum_k(Q^n)_{ik}s_k(Q)\le r_0s_i(Q^n)\le r_0^{n+1}$. Since $Q^0=I$ has row sums $1$, induction proves $s_i(Q^n)\le r_0^n$ for every $n\ge0$. Each entry of $Q^n$ is nonnegative and at most its row sum, so each entry series is bounded by $\sum_{n=0}^{\infty}r_0^n=1/(1-r_0)$ and converges.

For each integer $m\ge0$, multiplication and cancellation of adjacent terms give $$ (I-Q)\sum_{n=0}^{m}Q^n=I-Q^{m+1}, \qquad \left(\sum_{n=0}^{m}Q^n\right)(I-Q)=I-Q^{m+1}. $$ The row-sum bound implies every entry of $Q^{m+1}$ tends to $0$. Taking entrywise limits in these finite-dimensional matrix products gives $(I-Q)N=I$ and $N(I-Q)=I$. Thus $N$ is a two-sided inverse of $I-Q$, which proves the formula. $\square$

The proposition gives both a convergence check and a computation: when its row-sum hypothesis holds, calculate $I-Q$ and invert it. This hypothesis is sufficient, not necessary. A transient block may have a row sum equal to $1$ in one or more rows and still yield a convergent series; the criterion above simply does not decide those cases.

Worked Matrix Calculations

Worked Example: Two Transient States with Symmetric Moves

Consider the chain on $S=\{1,2,3\}$, where states $1,2$ are transient and state $3$ is absorbing. Its transition matrix is $$ P= \begin{bmatrix} \tfrac12&\tfrac14&\tfrac14\\ \tfrac14&\tfrac12&\tfrac14\\ 0&0&1 \end{bmatrix}. $$ Every row sums to $1$: the first two sums are $\tfrac12+\tfrac14+\tfrac14=1$, and the third is $0+0+1=1$. The transient block is $Q=\begin{bmatrix}\tfrac12&\tfrac14\\\tfrac14&\tfrac12\end{bmatrix}$, whose two row sums are each $\tfrac34<1$. The proposition therefore applies.

Subtract $Q$ from the identity and compute the determinant: $$ I-Q= \begin{bmatrix} \tfrac12&-\tfrac14\\ -\tfrac14&\tfrac12 \end{bmatrix}, \qquad \det(I-Q)=\tfrac14-\tfrac1{16}=\tfrac3{16}. $$ The inverse of a $2\times2$ matrix gives $$ N=(I-Q)^{-1} =\frac{16}{3} \begin{bmatrix} \tfrac12&\tfrac14\\ \tfrac14&\tfrac12 \end{bmatrix} = \begin{bmatrix} \tfrac83&\tfrac43\\ \tfrac43&\tfrac83 \end{bmatrix}. $$ Check: Multiplying the matrices, $$ (I-Q)N= \begin{bmatrix} \tfrac12\cdot\tfrac83-\tfrac14\cdot\tfrac43& \tfrac12\cdot\tfrac43-\tfrac14\cdot\tfrac83\\ -\tfrac14\cdot\tfrac83+\tfrac12\cdot\tfrac43& -\tfrac14\cdot\tfrac43+\tfrac12\cdot\tfrac83 \end{bmatrix} = \begin{bmatrix}1&0\\0&1\end{bmatrix}. $$ This verifies the inverse directly.

Worked Example: A One-Way Transient Transition

Let $S=\{1,2,3\}$, with states $1,2$ transient and state $3$ absorbing, and take $$ P= \begin{bmatrix} \tfrac12&\tfrac13&\tfrac16\\ 0&\tfrac13&\tfrac23\\ 0&0&1 \end{bmatrix}. $$ The row sums are $\tfrac12+\tfrac13+\tfrac16=1$, $0+\tfrac13+\tfrac23=1$, and $0+0+1=1$. Thus the transient block $$ Q=\begin{bmatrix}\tfrac12&\tfrac13\\0&\tfrac13\end{bmatrix} $$ has row sums $\tfrac56$ and $\tfrac13$, both less than $1$, so its series converges by the proposition.

First compute $$ I-Q=\begin{bmatrix}\tfrac12&-\tfrac13\\0&\tfrac23\end{bmatrix}. $$ Its determinant is $\tfrac12\cdot\tfrac23-0=\tfrac13$. Hence $$ N=(I-Q)^{-1} =\frac{1}{\tfrac13} \begin{bmatrix}\tfrac23&\tfrac13\\0&\tfrac12\end{bmatrix} = \begin{bmatrix}2&1\\0&\tfrac32\end{bmatrix}. $$ Check: $$ (I-Q)N= \begin{bmatrix} \tfrac12\cdot2+(-\tfrac13)\cdot0& \tfrac12\cdot1+(-\tfrac13)\cdot\tfrac32\\ 0\cdot2+\tfrac23\cdot0& 0\cdot1+\tfrac23\cdot\tfrac32 \end{bmatrix} = \begin{bmatrix}1&0\\0&1\end{bmatrix}. $$ The zero in the lower-left entry of $N$ is consistent with the zero transition probability from state $2$ to state $1$: no positive power of $Q$ can create such a transition.

Worked Example: One Transient State

Take $S=\{1,2,3\}$, with state $1$ transient and states $2,3$ absorbing: $$ P= \begin{bmatrix} \tfrac13&\tfrac13&\tfrac13\\ 0&1&0\\ 0&0&1 \end{bmatrix}. $$ The row sums are $\tfrac13+\tfrac13+\tfrac13=1$, $0+1+0=1$, and $0+0+1=1$. Here $Q=[\tfrac13]$, whose row sum is $\tfrac13<1$. The fundamental matrix is the scalar geometric series $$ N=\sum_{n=0}^{\infty}\left(\tfrac13\right)^n =\frac{1}{1-\tfrac13} =\tfrac32. $$ The inverse calculation agrees: $I-Q=[\tfrac23]$, and $(I-Q)^{-1}=[\tfrac32]$. Check: $(\tfrac23)(\tfrac32)=1$, as required.

The Finite-Sum Identity and a Common Error

The inversion method is grounded in the finite geometric-sum identity, which does not require a convergence assumption. It is useful to keep this finite identity separate from the infinite-series conclusion: the former is always an algebraic calculation, while the latter requires that the remainder $Q^{m+1}$ tends to zero.

Identity: For any square matrix $Q$ and integer $m\ge0$, $$ (I-Q)(I+Q+\cdots+Q^m)=I-Q^{m+1}. $$

Proof. Distribute $I-Q$ across the finite sum. The result is $$ (I+Q+\cdots+Q^m)-(Q+Q^2+\cdots+Q^{m+1}). $$ Every term $Q,Q^2,\ldots,Q^m$ occurs once with a positive sign and once with a negative sign, leaving $I-Q^{m+1}$. For $m=0$, the same calculation reads $(I-Q)I=I-Q$, so the identity includes the zero-power case. $\square$

Common mistake: inverting $Q$ instead of $I-Q$. In the first example, $Q$ has determinant $\tfrac14-\tfrac1{16}=\tfrac3{16}$, so $$ Q^{-1}= \begin{bmatrix}\tfrac83&-\tfrac43\\-\tfrac43&\tfrac83\end{bmatrix}. $$ This is not the fundamental matrix. The correct matrix is $(I-Q)^{-1}=\begin{bmatrix}\tfrac83&\tfrac43\\\tfrac43&\tfrac83\end{bmatrix}$. Indeed, multiplying the mistaken candidate by $I-Q$ gives $$ \begin{bmatrix}\tfrac12&-\tfrac14\\-\tfrac14&\tfrac12\end{bmatrix} \begin{bmatrix}\tfrac83&-\tfrac43\\-\tfrac43&\tfrac83\end{bmatrix} = \begin{bmatrix}\tfrac53&-\tfrac43\\-\tfrac43&\tfrac53\end{bmatrix}, $$ not the identity. The series is a geometric series in $Q$, so its inverse formula involves $I-Q$, not $Q$.

For any calculation, check the transition matrix row sums before extracting $Q$, identify the correct transient states, and then verify the proposed answer by multiplying it by $I-Q$. If the row-sum bound does not apply, do not infer convergence from the matrix-inversion calculation alone; the condition for the infinite series must be established by an appropriate argument.

Check Your Understanding

Use the definition and verify matrix calculations by substitution.

For a transient block $Q=\begin{bmatrix}\tfrac14&\tfrac14\\0&\tfrac12\end{bmatrix}$, check the row-sum condition and calculate $(I-Q)^{-1}$.
For the scalar block $Q=[\tfrac25]$, compute the fundamental matrix from the series and from matrix inversion. Do the answers agree?
State the finite geometric-sum identity and explain why it does not by itself establish convergence of the infinite series.
For $Q=\begin{bmatrix}\tfrac12&\tfrac12\\0&\tfrac13\end{bmatrix}$, does the strict row-sum criterion in the proposition apply? Explain what the criterion does and does not conclude.
Why is $Q^{-1}$ not the formula for the fundamental matrix?

The Fundamental Matrix of an Absorbing Chain

What You'll Learn