Why the Fundamental Matrix Exists

From Eventual Absorption to a Convergent Matrix Series

For a finite absorbing Markov chain, the fundamental matrix is defined by the series \(I+Q+Q^2+\cdots\), where \(Q\) records transitions among the transient states. The definition is useful only if this series converges. The key point is that almost-sure absorption makes the probability of still being among the transient states tend to zero. Finiteness then upgrades that state-by-state decay to a common geometric bound, which is strong enough to prove both convergence and invertibility.

Let \((X_n)_{n\ge0}\) be a discrete-time Markov chain on a finite state space \(S=T\cup A\), with \(T\) and \(A\) disjoint and \(T\ne\varnothing\). Work on a probability space \((\Omega,\mathcal{F},\mathbb{P})\); write \(\mathbb{P}_i\) for the law of the chain started at \(i\). Assume that every state in \(A\) is absorbing: once \(X_n\in A\), the chain remains in \(A\). Order the states in \(T\) first and write the transition matrix in block form as

Here \(Q=(q_{ij})_{i,j\in T}\) gives transitions within \(T\), and \(R\) gives transitions from \(T\) to \(A\). Since every row of \(P\) sums to \(1\), \(Q\) is nonnegative and each of its row sums is at most \(1\). Such a matrix is called substochastic. Define the absorption time \(T_A=\inf\{n\ge0:X_n\in A\}\), where \(\inf\varnothing=\infty\). The assumption needed here is absorption almost surely from every transient-block state: \(\mathbb{P}_i(T_A<\infty)=1\) for each \(i\in T\).

A Geometric Bound Gives the Inverse

For a matrix \(B\), use the maximum row-sum norm \(\|B\|_\infty=\max_i\sum_j|b_{ij}|\). It satisfies \(\|BC\|_\infty\le\|B\|_\infty\|C\|_\infty\): for each row \(i\), the triangle inequality gives \(\sum_j|\sum_k b_{ik}c_{kj}|\le\sum_k|b_{ik}|\sum_j|c_{kj}|\le\|C\|_\infty\sum_k|b_{ik}|\). This norm lets us turn a bound on one power of \(Q\) into a bound on the whole series.

Proof. Since \(Q\) is substochastic, \(\|Q\|_\infty\le1\), so \(\|Q^r\|_\infty\le1\) for every integer \(r\ge0\), by submultiplicativity. Write \(n=kL+r\), where \(k\ge0\) and \(0\le r<L\). Then \(Q^n=(Q^L)^kQ^r\), so \(\|Q^n\|_\infty\le\theta^k\). Thus the sum of the norms over the \(L\) terms in block \(k\) is at most \(L\theta^k\), and \(\sum_{k\ge0}L\theta^k=L/(1-\theta)<\infty\). The matrix series therefore converges. For its partial sums \(S_m=\sum_{n=0}^{m}Q^n\), multiplication and cancellation give \((I-Q)S_m=S_m(I-Q)=I-Q^{m+1}\). The same block bound implies \(\|Q^{m+1}\|_\infty\to0\). Taking limits on both sides yields \((I-Q)\sum_{n\ge0}Q^n=\big(\sum_{n\ge0}Q^n\big)(I-Q)=I\), proving that the sum is the inverse. \(\square\)

Proof. For \(i\in T\) and \(n\ge0\), the sum of row \(i\) of \(Q^n\) is the probability of staying in \(T\) through time \(n\): \(\sum_{j\in T}(Q^n)_{ij}=\mathbb{P}_i(T_A>n)\). This follows by summing the probabilities of the disjoint events \(X_n=j\) while \(X_0,\ldots,X_n\in T\). Almost-sure absorption implies \(\mathbb{P}_i(T_A>n)\to0\) for each \(i\). Because \(T\) is finite, choose one integer \(L\ge1\) large enough that \(\mathbb{P}_i(T_A>L)\le\tfrac12\) for every \(i\in T\). Hence \(\|Q^L\|_\infty\le\tfrac12\), and the lemma proves convergence of the series and \(N=(I-Q)^{-1}\).

It remains to show the spectral-radius claim. Let \(\lambda\) be any complex eigenvalue of \(Q\), and take a nonzero complex eigenvector \(x\) with \(Qx=\lambda x\). The maximum-coordinate norm on vectors satisfies \(\|Q^Lx\|_\infty\le\|Q^L\|_\infty\|x\|_\infty\). Therefore \(|\lambda|^L\|x\|_\infty=\|Q^Lx\|_\infty\le\tfrac12\|x\|_\infty\). Since \(x\ne0\), this gives \(|\lambda|\le(1/2)^{1/L}<1\). It holds for every eigenvalue, so \(\rho(Q)<1\). \(\square\)

The finite-state assumption matters at the step where one common \(L\) is chosen. Almost-sure absorption gives decay separately from each state; finiteness lets us choose a single time that works for all states. The geometric estimate then does more than show that the entries of the series have finite limits: it controls the matrix powers strongly enough to justify the inverse by telescoping.

Worked Checks of the Argument

A Common Mistake and Its Correction

A tempting but incorrect argument is: “Some row of \(Q\) sums to \(1\), so \(\|Q\|_\infty=1\); therefore the series cannot converge.” A norm equal to \(1\) at the first step does not imply that later powers remain large. In the preceding example, \(\|Q\|_\infty=1\), but \(Q^3=0\), so the series terminates. The correct test is not whether every row loses probability in one step. Instead, use almost-sure absorption and finiteness to find a common block length \(L\) for which every row sum of \(Q^L\) is at most \(\tfrac12\). That block contraction is what proves convergence.

Conversely, the absorption condition cannot simply be dropped. If state \(1\) is closed and nonabsorbing while \(a\) is absorbing, then \(P=\begin{bmatrix}1&0\\0&1\end{bmatrix}\) with \(T=\{1\}\), \(A=\{a\}\), and \(Q=[1]\). The rows of \(P\) sum to \(1\), but \(\mathbb{P}_1(T_A<\infty)=0\), \(\rho(Q)=1\), and \(\sum_{n\ge0}Q^n\) diverges. The row-stochastic property alone is not enough: the key hypothesis is almost-sure absorption from every state in \(T\).

If \(T\) is empty, there is no transient block to analyze and the assertion is vacuous; the theorem above addresses the nonempty case. For a nonempty transient block, its practical conclusion is precise: almost-sure absorption guarantees that \(I-Q\) is invertible and that its inverse is obtained by the convergent power series. The later interpretation of the entries of \(N\) is separate from this existence argument.