An Exact-Arithmetic Workflow
Absorbing-chain calculations often end with several related quantities: expected visits to transient states, probabilities of absorption in each absorbing state, and expected time to absorption. A numerical answer is more trustworthy when it comes with independent checks. This tutorial develops a practical workflow: put the transition matrix in canonical order, solve using exact rational arithmetic, and verify the result through matrix residuals, probability sums, and a small simulation.
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})\). Suppose its states are ordered with \(r\) transient states first and \(a\) absorbing states last. In this order, write its row-stochastic transition matrix in block form as
Here \(Q\) is the \(r\times r\) matrix of transitions among transient states, \(R\) is the \(r\times a\) matrix of transitions from transient to absorbing states, and \(I\) is the \(a\times a\) identity matrix. Each row of \(Q\) and \(R\), taken together, sums to \(1\); each absorbing-state row also sums to \(1\). The fundamental matrix is \(N=(I-Q)^{-1}\), when this inverse exists. Its entry \(N_{ij}\) is the expected number of visits to transient state \(j\), starting from transient state \(i\), before absorption. The matrix \(B=NR\) gives the probabilities of absorption in each absorbing state, and the column vector \(t=N\mathbf{1}\) gives expected times to absorption, where \(\mathbf{1}\) is a column of ones.
Exact arithmetic matters because rounded decimals can make a correct residual look nonzero, or make an incorrect result appear close enough. A rational-arithmetic implementation stores, for example, \(\tfrac14\) as the numerator-denominator pair \((1,4)\), and performs row reduction without converting to floating point.
Why the Checks Work
The calculations are linear solves, not separate formulas to memorize. One solves \((I-Q)N=I\) for \(N\), \(B=QB+R\) for absorption probabilities, and \((I-Q)t=\mathbf{1}\) for expected times. The following result explains why these equations provide both a computation and a check.
Proof. Since \(I-Q\) is invertible, multiplying \((I-Q)N=I\) on the left by \((I-Q)^{-1}\) gives \(N=(I-Q)^{-1}\), and this is the unique solution. For the second equation, multiply \((I-Q)B=R\) on the left by \(N=(I-Q)^{-1}\). This gives \(B=NR\); invertibility also implies uniqueness. For the third equation, the same multiplication gives \(t=N\mathbf{1}\), again uniquely. Conversely, substituting these three expressions into their respective equations gives \(I\), \(R\), and \(\mathbf{1}\), because \((I-Q)N=I\). Thus the residual checks test the defining equations, and the solutions are unique. \(\square\)
In an absorbing chain where absorption occurs with probability \(1\) from every transient state, the earlier material on the fundamental matrix establishes that \(I-Q\) is invertible. The computational procedure below still needs to respect that condition: if absorption can fail, finite expected absorption times or an inverse need not exist.
Confirm that every row of \(P\) sums to \(1\), that the absorbing states have the intended absorbing rows, and that the transient and absorbing states are in the stated order.
Read off \(Q\) and \(R\), then form \(I-Q\). Keep all entries as exact fractions.
Use exact Gaussian elimination or exact matrix inversion to obtain \(N\), \(B\), and \(t\). The row operations in Gaussian elimination preserve the solution set because each row operation replaces a system by an equivalent system.
Compute the residuals \((I-Q)N-I\), \(B-QB-R\), and \(t-\mathbf{1}-Qt\). Check that the rows of \(B\) sum to \(1\) when certain absorption is assumed.
Worked Calculations and Audits
Worked Example: Two Transient States and Two Absorbing Outcomes
Consider a chain on \(S=\{1,2,3,4\}\), with states \(1,2\) transient and states \(3,4\) absorbing. From state \(1\), the probabilities of moving to states \(1,2,3,4\) are \(\tfrac12,\tfrac14,\tfrac14,0\). From state \(2\), they are \(\tfrac13,\tfrac13,0,\tfrac13\). The absorbing states stay where they are. The transient rows sum to \(\tfrac12+\tfrac14+\tfrac14+0=1\) and \(\tfrac13+\tfrac13+0+\tfrac13=1\); each absorbing row sums to \(1\).
The blocks are \(Q=\begin{bmatrix}\tfrac12&\tfrac14\\\tfrac13&\tfrac13\end{bmatrix}\) and \(R=\begin{bmatrix}\tfrac14&0\\0&\tfrac13\end{bmatrix}\). Thus
The determinant is nonzero, so the inverse exists. The two-by-two inverse formula gives
Multiplying \(N\) by \(R\) gives the absorption probabilities:
The expected times are \(t=N\mathbf{1}=(\tfrac83+1,\tfrac43+2)^{\mathsf T}=(\tfrac{11}3,\tfrac{10}3)^{\mathsf T}\). Check the inverse by multiplying:
For the absorption check, the first row of \(QB+R\) is \((\tfrac13+\tfrac1{12}+\tfrac14,\ \tfrac16+\tfrac16)=(\tfrac23,\tfrac13)\); the second is \((\tfrac29+\tfrac19,\ \tfrac19+\tfrac29+\tfrac13)=(\tfrac13,\tfrac23)\). These are the rows of \(B\). Each row sums to \(1\): \(\tfrac23+\tfrac13=1\) and \(\tfrac13+\tfrac23=1\). Finally, \(1+Qt\) has entries \(1+\tfrac12\cdot\tfrac{11}3+\tfrac14\cdot\tfrac{10}3=\tfrac{11}3\) and \(1+\tfrac13\cdot\tfrac{11}3+\tfrac13\cdot\tfrac{10}3=\tfrac{10}3\), as required.
Worked Example: A Three-State Transient Block
Let the transient states be \(1,2,3\), and let the absorbing states be \(4,5\). State \(1\) moves to state \(2\) with probability \(\tfrac12\) and to state \(4\) with probability \(\tfrac12\). State \(2\) moves to state \(3\) with probability \(\tfrac13\) and to state \(5\) with probability \(\tfrac23\). State \(3\) moves to state \(4\) with probability \(\tfrac14\) and to state \(5\) with probability \(\tfrac34\). The transient-row sums are \(\tfrac12+\tfrac12=1\), \(\tfrac13+\tfrac23=1\), and \(\tfrac14+\tfrac34=1\); both absorbing rows sum to \(1\).
In the state order \(1,2,3,4,5\), the blocks are
Here \(I-Q=\begin{bmatrix}1&-\tfrac12&0\\0&1&-\tfrac13\\0&0&1\end{bmatrix}\). Solving \((I-Q)N=I\) by back-substitution gives
For example, the first row of the product \((I-Q)N\) is \((1,\tfrac12-\tfrac12,\tfrac16-\tfrac12\cdot\tfrac13)=(1,0,0)\), and the second is \((0,1,\tfrac13-\tfrac13)=(0,1,0)\); the third is \((0,0,1)\). Thus the inverse residual is zero. Multiplication gives
Check the absorption equations row by row. The first row of \(QB+R\) is \((\tfrac12\cdot\tfrac1{12}+\tfrac12,\ \tfrac12\cdot\tfrac{11}{12})=(\tfrac{13}{24},\tfrac{11}{24})\). The second is \((\tfrac13\cdot\tfrac14,\ \tfrac13\cdot\tfrac34+\tfrac23)=(\tfrac1{12},\tfrac{11}{12})\). The third is the third row of \(R\), since the third row of \(Q\) is zero. The row sums of \(B\) are \(\tfrac{13}{24}+\tfrac{11}{24}=1\), \(\tfrac1{12}+\tfrac{11}{12}=1\), and \(\tfrac14+\tfrac34=1\). The time check gives \(1+\tfrac12\cdot\tfrac43=\tfrac53\), \(1+\tfrac13\cdot1=\tfrac43\), and \(1+0=1\).
Worked Example: Combining Results for an Initial Distribution
Use the three-transient-state chain above, now with initial distribution \(\mu=(\tfrac12,\tfrac12,0)\) over its transient states. The initial probabilities sum to \(\tfrac12+\tfrac12+0=1\). Since distributions are row vectors, the absorption-outcome distribution is \(\mu B\), and the expected time is \(\mu t\).
For the two absorbing outcomes,
The two probabilities sum to \(\tfrac5{16}+\tfrac{11}{16}=1\). The expected absorption time is \(\mu t=\tfrac12\cdot\tfrac53+\tfrac12\cdot\tfrac43=\tfrac56+\tfrac23=\tfrac32\). As a separate check, state \(1\) takes one step and then either absorbs or proceeds to state \(2\); its expected time is \(\tfrac53\). Starting in state \(2\), the expected time is \(\tfrac43\). Averaging these two conditional expectations with initial weights \(\tfrac12,\tfrac12\) gives \(\tfrac12\cdot\tfrac53+\tfrac12\cdot\tfrac43=\tfrac32\), agreeing with the matrix calculation.
Simulation as a Diagnostic
Simulation can reveal a coding or state-ordering error, but a finite collection of simulated paths does not verify an exact probability or expectation. For example, in the first chain, consider six possible sample paths started from state \(1\), recording the absorbing state and the number of transitions until absorption:
| Path | Absorbing state | Steps |
|---|---|---|
| \(1\to3\) | 3 | 1 |
| \(1\to2\to4\) | 4 | 2 |
| \(1\to1\to3\) | 3 | 2 |
| \(1\to2\to2\to4\) | 4 | 3 |
| \(1\to1\to2\to3\) | 3 | 3 |
| \(1\to2\to1\to2\to4\) | 4 | 4 |
Every transition listed has positive probability under the stated matrix. These six paths have an empirical fraction \(\tfrac36=\tfrac12\) ending in state \(3\), and their empirical mean duration is \((1+2+2+3+3+4)/6=\tfrac{15}6=\tfrac52\). The exact calculations instead give probability \(\tfrac23\) of absorption in state \(3\) and expected duration \(\tfrac{11}3\). This difference is not a contradiction: a small sample can differ substantially from the exact values. A useful simulation check is to compare larger-run frequencies and averages with the exact answers, while retaining the exact residual checks as the decisive algebraic audit.
A Common Matrix-Ordering Mistake
Because both \(N\) and \(R\) are square in the first example, the incorrect product \(RN\) is dimensionally allowed. But absorption probabilities are \(B=NR\): the chain first accumulates expected visits among transient states, then transitions from those states into absorbing states. Reversing the order gives
The first row sums to \(\tfrac23+\tfrac14=\tfrac{11}{12}\), not \(1\), and the second sums to \(\tfrac49+\tfrac23=\tfrac{10}{9}\), greater than \(1\). These are not probability distributions. The correction is to use \(NR\), then check both \(B=QB+R\) and that each row of \(B\) sums to \(1\). If the row sums do not equal \(1\), first check the state ordering, block extraction, multiplication order, and whether certain absorption is actually part of the assumptions.
Check Your Understanding
Use exact fractions throughout, and state which equation or check supports each answer.
- For an absorbing chain in canonical form, what dimensions do \(Q\), \(R\), \(N\), and \(B\) have if there are \(r\) transient and \(a\) absorbing states?
- Suppose an exact computation gives a matrix \(\widehat{N}\). Which residual should be zero if \(\widehat{N}\) is the fundamental matrix?
- In the three-transient-state example, compute the expected absorption time if the initial distribution is \((0,0,1)\), and verify it from the third component of \(t\).
- Why does a simulated absorption fraction of \(\tfrac12\) in six paths not contradict the exact probability \(\tfrac23\) in the first example?
- In what order should \(N\) and \(R\) be multiplied to obtain absorption probabilities, and name one check that can expose reversing the order.