Putting the Chain in Canonical Order
When a chain has several transient states and several absorbing outcomes, the calculations become easier to read if the states are ordered by role. The transient states come first, followed by the absorbing states. In this form, one block records moves among transient states, another records moves from transient to absorbing states, and the remaining blocks show that absorption is permanent.
Let \((X_n)_{n\ge0}\) be a discrete-time Markov chain on a finite state space \(S\), on a probability space \((\Omega,\mathcal{F},\mathbb{P})\). Write \(\mathcal{F}_n=\sigma(X_0,\ldots,X_n)\) for its natural filtration and \(P=(p_{ij})\) for its row-stochastic transition matrix. A state \(a\) is absorbing if \(p_{aa}=1\). Suppose there are three transient states and two absorbing states. After ordering the states as transient states \(1,2,3\), then absorbing states \(4,5\), the matrix has the form below.
If a chain is not already written in this order, apply the same permutation to its rows and columns so the transient states are listed first. This changes only the state labels’ order, not the transitions themselves. Since each row of \(P\) sums to \(1\), the rows of \(Q\) and \(R\) together also sum to \(1\); the rows of \(Q\) alone may sum to less than \(1\), because some probability can move directly to absorption.
Proof. First, the series defining \(N\) converges. For each transient state \(i\), absorption with probability \(1\) implies there is an integer \(n_i\) for which \(\mathbb{P}_i(T_A\le n_i)>0\), where \(A=\{4,5\}\) and \(T_A=\inf\{n\ge0:X_n\in A\}\). Since there are finitely many transient states, take \(m=\max_i n_i\) and \(\delta=\min_i\mathbb{P}_i(T_A\le m)>0\). From any transient state, the probability of remaining transient for the next \(m\) steps is at most \(1-\delta\). By the Markov property, the probability of remaining transient for \(km\) steps is at most \((1-\delta)^k\). Thus the row sums of \(Q^n\) decay geometrically in blocks of \(m\), so \(\sum_{n\ge0}Q^n\) converges entrywise. Multiplying its finite partial sums by \(I-Q\) gives \((I-Q)\sum_{n=0}^{r}Q^n=I-Q^{r+1}\); the decay gives \(Q^{r+1}\to0\). Hence the series is \((I-Q)^{-1}\).
Starting from a transient state, the probability of still being transient after \(n\) steps and then moving to an absorbing state on the next step is recorded by \(Q^nR\). Absorption at different step numbers is disjoint, so summing over \(n\ge0\) gives \(B=\sum_{n\ge0}Q^nR=NR\). Also, \(T_A=\sum_{n\ge0}\mathbf{1}_{\{T_A>n\}}\). Taking expectations, \(\mathbb{E}_i[T_A]=\sum_{n\ge0}\mathbb{P}_i(T_A>n)\). The vector of these probabilities at step \(n\) is \(Q^n\mathbf{1}\), so \(t=\sum_{n\ge0}Q^n\mathbf{1}=N\mathbf{1}\). \(\square\)
A Three-State, Two-Outcome Calculation
Worked Example: Compute the Fundamental Matrix and Both Outcomes
Consider states \(1,2,3\) as transient and states \(4,5\) as absorbing. The transition matrix is
Before using it, check the row sums: row \(1\) is \(\tfrac12+\tfrac14+\tfrac14=1\); row \(2\) is \(\tfrac12+\tfrac14+\tfrac14=1\); row \(3\) is \(\tfrac12+\tfrac14+\tfrac14=1\); and rows \(4\) and \(5\) each sum to \(1\). The last two states are absorbing. From each transient state there is a positive probability of absorption within one step, so absorption occurs eventually with probability \(1\). The canonical blocks are
Each row of \(Q\) plus the corresponding row of \(R\) sums to \(1\): the totals are \(\tfrac34+\tfrac14\), \(\tfrac34+\tfrac14\), and \(\tfrac12+\tfrac12\). To find \(N\), first subtract \(Q\) from the identity:
For example, the first row of \((I-Q)N\) is \((1,\tfrac12-\tfrac12, \tfrac14-\tfrac14)=(1,0,0)\); the second row is \((0,1,\tfrac12-\tfrac12)=(0,1,0)\); the third row is \((0,0,1)\). Thus the proposed inverse checks by multiplication. The entries also have a visit interpretation: starting from state \(1\), the expected numbers of visits to transient states \(1,2,3\), counting the initial state, are \(2,1,\tfrac12\).
Now multiply \(N\) by \(R\). For the first column, the three entries are \(2(\tfrac14)+1(0)+\tfrac12(\tfrac14)=\tfrac58\), \(0(\tfrac14)+2(0)+1(\tfrac14)=\tfrac14\), and \(0+0+2(\tfrac14)=\tfrac12\). For the second column they are \(2(0)+1(\tfrac14)+\tfrac12(\tfrac14)=\tfrac38\), \(0+2(\tfrac14)+1(\tfrac14)=\tfrac34\), and \(2(\tfrac14)=\tfrac12\). Therefore
Each row sums to \(1\): \(\tfrac58+\tfrac38=1\), \(\tfrac14+\tfrac34=1\), and \(\tfrac12+\tfrac12=1\). The first row, for instance, says that starting from state \(1\), the eventual absorption probabilities in states \(4\) and \(5\) are \(\tfrac58\) and \(\tfrac38\).
Finally, multiply \(N\) by the all-ones column. This gives the expected absorption times \(t_1=2+1+\tfrac12=\tfrac72\), \(t_2=0+2+1=3\), and \(t_3=2\).
Check: The first-step equations are \(t_1=1+\tfrac12t_1+\tfrac14t_2\), \(t_2=1+\tfrac12t_2+\tfrac14t_3\), and \(t_3=1+\tfrac12t_3\). Substitution gives \(1+\tfrac74+\tfrac34=\tfrac72\), \(1+\tfrac32+\tfrac12=3\), and \(1+1=2\), as required.
Changing the Starting Distribution
The matrix \(B\) gives one row for each transient starting state. If the initial state is random, combine those rows using the initial distribution. Distributions are row vectors, so the multiplication order is initial distribution first, then the matrix of absorption probabilities.
Worked Example: A Uniform Transient Starting State
Use the checked transition matrix and absorption probabilities above. Let the initial distribution assign probability \(\tfrac13\) to each transient state and zero to the absorbing states: \(\mu=(\tfrac13,\tfrac13,\tfrac13,0,0)\). The three entries sum to \(1\). Its transient part is \(\mu_T=(\tfrac13,\tfrac13,\tfrac13)\). The probability of absorption in state \(4\) is
The probability of absorption in state \(5\) is \(\tfrac13\cdot\tfrac38+\tfrac13\cdot\tfrac34+\tfrac13\cdot\tfrac12=\tfrac{9}{72}+\tfrac{18}{72}+\tfrac{12}{72}=\tfrac{39}{72}=\tfrac{13}{24}\). These probabilities sum to \(\tfrac{11}{24}+\tfrac{13}{24}=1\). The expected time to absorption is the same weighted average of the entries of \(t\):
Check: The mean is between the smallest and largest state-specific means, \(2\) and \(\tfrac72\), and the weighted calculation gives \(\tfrac{17}{6}\), which lies in that interval.
Checking an Outcome with First-Step Equations
Worked Example: Probability of Absorbing in State 4 from State 2
Let \(h_i=\mathbb{P}_i(X_{T_A}=4)\) for transient states \(i=1,2,3\). The value sought is \(h_2\). Conditioning on the first transition gives
The final \(\tfrac14\) in the first and third equations is the direct probability of moving to state \(4\); state \(5\) contributes zero to this particular outcome. Solve from the last equation: \(\tfrac12h_3=\tfrac14\), so \(h_3=\tfrac12\). Then \(\tfrac12h_2=\tfrac14h_3=\tfrac18\), so \(h_2=\tfrac14\). The first equation gives \(\tfrac12h_1=\tfrac14h_2+\tfrac14=\tfrac1{16}+\tfrac14=\tfrac5{16}\), hence \(h_1=\tfrac58\).
Check: Substitution into the middle equation gives \(\tfrac12(\tfrac14)+\tfrac14(\tfrac12)=\tfrac18+\tfrac18=\tfrac14=h_2\). The result agrees with the state-2, state-4 entry of \(B\).
Why the Calculations Work—and a Common Error
The fundamental matrix and the absorption-probability matrix answer different questions. \(N\) counts expected visits to transient states before absorption; \(B=NR\) gives probabilities of the absorbing outcomes. Expected time is obtained by adding expected visits across transient states, \(N\mathbf{1}\), not by summing the outcome probabilities. As a consistency check, every row of \(B\) must sum to \(1\) when absorption is certain.
A common mistake is to omit the initial visit when calculating absorption time. In this example, using \((N-I)\mathbf{1}\) would give \((\tfrac52,2,1)^\mathsf{T}\), which is too small by \(1\) in every entry. The chain takes at least one transition before it can leave a transient starting state; \(N\) counts the visit at time \(0\), and that initial visit is part of the expected number of steps until absorption. The correct calculation is \(N\mathbf{1}=(\tfrac72,3,2)^\mathsf{T}\), verified by the first-step equations.
These calculations depend on absorption occurring with probability \(1\) from each transient state. If a transient state can lead into a closed class that avoids both absorbing states, the series \(\sum_{n\ge0}Q^n\) need not converge, and the inverse-based formulas cannot be used as finite expected counts without further analysis. Check the state structure and the row sums before computing \(N\).
Check Your Understanding
Use the definitions and calculations above to answer these questions.
- In canonical order, what do the blocks \(Q\) and \(R\) record?
- For the worked chain, calculate the expected number of visits to state \(2\) when starting from state \(1\), counting the initial time if applicable.
- Starting from state \(3\), what is the probability of eventual absorption in state \(5\)? Check it against the row sum of the two outcome probabilities.
- Why does \(N\mathbf{1}\) give expected absorption times, whereas \(NR\) gives absorption probabilities?
- What assumption about the transient states is needed for the finite fundamental-matrix calculation?