From Transient Visits to Absorption Time
For a finite absorbing Markov chain, the fundamental matrix records how often the chain visits each transient state before absorption. Summing a row of that matrix therefore has a direct interpretation: it counts the expected total number of visits to transient states from a specified starting state. Since each step before absorption is spent in exactly one transient state, that row sum gives the expected number of steps until absorption. This tutorial develops that calculation and shows how to average it when the starting state is random.
Work on a probability space \((\Omega,\mathcal{F},\mathbb{P})\). Let \((X_n)_{n\ge0}\) be a discrete-time Markov chain on a finite state space \(S\), with row-stochastic transition matrix \(P=(p_{ij})\). A state is absorbing if, once entered, the chain stays there with probability \(1\). Suppose the states are ordered with the \(r\) transient states first and the \(a\) absorbing states last. In canonical form,
where \(Q\) is the \(r\times r\) transient-to-transient block, \(R\) gives transitions from transient to absorbing states, and \(I\) is the \(a\times a\) identity matrix. The matrix is row-stochastic: each row of \(Q\), together with its corresponding entries of \(R\), sums to \(1\), and each absorbing row sums to \(1\). Assume the transient states are genuinely transient, so absorption occurs with probability \(1\) from each of them and the fundamental matrix exists:
For a chain started in a transient state, define the absorption time by \(T=\inf\{n\ge0:X_n\text{ is absorbing}\}\). In particular, if the initial state is transient, then \(T\ge1\). Let \(\mathbf{1}\) denote the \(r\)-dimensional column vector of ones.
Proof. First start from transient state \(i\). For each integer \(n\ge0\), the event \(T>n\) means that the chain is still transient at time \(n\). The transient block of \(P^n\) is \(Q^n\), so \(\mathbb{P}_i(T>n)=\sum_j(Q^n)_{ij}\). For a nonnegative integer-valued random variable, \(T=\sum_{n\ge0}\mathbf{1}_{\{T>n\}}\): if \(T=m\), exactly the terms \(n=0,\ldots,m-1\) equal \(1\). Taking expectations and summing nonnegative terms gives \(\mathbb{E}_i[T]=\sum_{n\ge0}\mathbb{P}_i(T>n)=\sum_{n\ge0}\sum_j(Q^n)_{ij}\). By the defining series for \(N\), this is \(\sum_jN_{ij}\), the \(i\)th entry of \(N\mathbf{1}\). For a general initial distribution, the chain starts in a transient state with probabilities \(\alpha\); if it starts in an absorbing state, \(T=0\). Averaging the transient-state expectations therefore gives \(\mathbb{E}_{\beta}[T]=\alpha\mathbf{t}=\alpha N\mathbf{1}\). This proves both claims. \(\square\)
The \(n=0\) term matters: \(Q^0=I\) counts the initial transient-state visit. That visit corresponds to the first step still being ahead, so it must be included when counting steps to absorption. The next examples show how to calculate and check the formula.
Worked Example: Two Transient States and an Arbitrary Initial Distribution
Consider states \(1,2\) as transient and states \(3,4\) as absorbing, with transition matrix
The first row sums to \(\tfrac12+\tfrac14+\tfrac18+\tfrac18=1\); the second sums to \(\tfrac14+\tfrac14+\tfrac14+\tfrac14=1\); each absorbing row sums to \(1\). Thus the transition data are row-stochastic. Here
The determinant of \(I-Q\) is \(\tfrac12\cdot\tfrac34-(-\tfrac14)(-\tfrac14)=\tfrac38-\tfrac1{16}=\tfrac5{16}\). Therefore
Its row sums give \(t_1=\tfrac{12}{5}+\tfrac45=\tfrac{16}{5}\) and \(t_2=\tfrac45+\tfrac85=\tfrac{12}{5}\) expected steps. To check the inverse, multiply by \(I-Q\): the four entries of \(N(I-Q)\) are \(\tfrac65-\tfrac15=1\), \(-\tfrac35+\tfrac35=0\), \(\tfrac25-\tfrac25=0\), and \(-\tfrac15+\tfrac65=1\). The product is \(I\).
Now take the initial distribution \(\beta=(\tfrac13,\tfrac13,\tfrac16,\tfrac16)\), whose entries sum to \(1\). Its transient part is \(\alpha=(\tfrac13,\tfrac13)\). Hence
The two absorbing starting states contribute zero: their combined initial probability is \(\tfrac16+\tfrac16=\tfrac13\), and the formula averages the transient-state times using only the transient entries of \(\beta\), without renormalizing them. As a check, the transient probabilities sum to \(\tfrac23\), and \(\tfrac13\cdot\tfrac{16}{5}+\tfrac13\cdot\tfrac{12}{5}+\tfrac16\cdot0+\tfrac16\cdot0=\tfrac{28}{15}\), as required.
Worked Example: A Single Transient State
Suppose the chain has a transient state \(1\) and an absorbing state \(2\), with transition matrix
The transient row sums to \(\tfrac23+\tfrac13=1\), and the absorbing row sums to \(1\). The transient block is \(Q=[\tfrac23]\), so \(I-Q=[\tfrac13]\) and \(N=[3]\). Thus \(N\mathbf{1}=[3]\): starting in state \(1\), the mean number of steps to absorption is \(3\). If the initial distribution is \(\beta=(\tfrac34,\tfrac14)\), then \(\alpha=[\tfrac34]\) and \(\mathbb{E}_{\beta}[T]=\tfrac34\cdot3=\tfrac94\). Substituting the result into the formula checks the calculation directly. The initially absorbing mass contributes \(\tfrac14\cdot0=0\).
Worked Example: Three Transient States in Sequence
Consider states \(1,2,3\) as transient and state \(4\) as absorbing, with
The first three rows sum respectively to \(\tfrac12+\tfrac14+\tfrac14=1\), \(\tfrac13+\tfrac13+\tfrac13=1\), and \(\tfrac14+\tfrac34=1\); the last row sums to \(1\). The transient block and its complement are
Inverting this upper-triangular matrix gives
For verification, the diagonal entries of \(N(I-Q)\) are \(2\cdot\tfrac12=1\), \(\tfrac32\cdot\tfrac23=1\), and \(\tfrac43\cdot\tfrac34=1\). Its off-diagonal entries above the diagonal are \(2(-\tfrac14)+\tfrac34(\tfrac23)=-\tfrac12+\tfrac12=0\), \(\tfrac32(-\tfrac13)+\tfrac23(\tfrac34)=-\tfrac12+\tfrac12=0\), and \(\tfrac13(\tfrac34)+\tfrac34(-\tfrac13)=\tfrac14-\tfrac14=0\); entries below the diagonal are zero. Thus \(N(I-Q)=I\).
The expected times are the row sums: \(t_1=2+\tfrac34+\tfrac13=\tfrac{37}{12}\), \(t_2=\tfrac32+\tfrac23=\tfrac{13}{6}\), and \(t_3=\tfrac43\). Starting in state \(1\), the result is \(\tfrac{37}{12}\) steps. For the initial distribution \((\tfrac12,\tfrac13,\tfrac16,0)\), the mean is \(\tfrac12\cdot\tfrac{37}{12}+\tfrac13\cdot\tfrac{13}{6}+\tfrac16\cdot\tfrac43=\tfrac{37}{24}+\tfrac{13}{18}+\tfrac29=\tfrac{179}{72}\). The initial probabilities sum to \(\tfrac12+\tfrac13+\tfrac16=1\), and the weighted sum gives the stated mean.
Reading and Using the Formula
For each transient starting state, the corresponding row of \(N\) gives expected visits to the transient states, including the visit at time \(0\). Adding those entries counts all transient visits in expectation. A path that starts transient and is absorbed at time \(T\) has transient states at exactly times \(0,1,\ldots,T-1\), so it has exactly \(T\) such visits. This is why the row sum counts steps, rather than steps minus one. The theorem also shows why the initial distribution is handled by a row-vector product: \(\alpha\) weights the starting-state times, and \(\alpha N\mathbf{1}\) is a scalar.
A practical calculation can be organized as follows:
Confirm the transition matrix is row-stochastic and place transient states before absorbing states.
Keep only transitions from transient states to transient states.
Find \((I-Q)^{-1}\), or use the fundamental matrix already available for the chain.
Compute \(N\mathbf{1}\) for each transient starting state, then multiply on the left by the transient part \(\alpha\) of the initial row distribution.
Check the transition row sums, the matrix inverse by multiplication, and that the initial probabilities sum to \(1\).
Common mistake: using the initial distribution as a column vector. In the three-transient-state example, starting at state \(1\) means \(\alpha=(1,0,0)\). The correct calculation is \(\alpha N\mathbf{1}\), which is the first row sum \(2+\tfrac34+\tfrac13=\tfrac{37}{12}\). If one incorrectly computes \(N\alpha^{\mathsf T}\), the result is the column \((2,0,0)^{\mathsf T}\), whose entries sum to \(2\), not \(\tfrac{37}{12}\). The convention is that distributions are row vectors; their multiplication by \(N\) is on the left.
A second off-by-one error is to subtract \(1\) from the row sum because the fundamental matrix includes a visit at time \(0\). That visit must stay in the count: in the single-transient-state example, \(N=[3]\), and the expected absorption time is \(3\), not \(3-1=2\). Conversely, if a chain starts in an absorbing state, its absorption time under \(T=\inf\{n\ge0:X_n\text{ is absorbing}\}\) is \(0\); that mass contributes zero, not one.
The assumption that the transient block really is transient is also essential. For example, a state that stays in itself with probability \(1\) is not transient: its \(Q=[1]\) makes \(I-Q=[0]\) noninvertible, and absorption from that state never occurs. The fundamental-matrix calculation is not defined there. Before applying the formula, check that the selected transient states satisfy the absorbing-chain assumptions.
Check Your Understanding
Use the row-vector convention and verify calculations by substitution.
- For a chain with transient block \(Q=[\tfrac34]\) and one absorbing state, compute \(N\) and the expected absorption time from the transient state.
- In the first worked example, what is the expected absorption time if the initial distribution is concentrated on state \(2\)?
- For the three-transient-state example, compute the mean absorption time from initial distribution \((0,\tfrac12,\tfrac12,0)\).
- Why does \(N\mathbf{1}\) count steps to absorption rather than the number of steps after the first transition?
- What goes wrong with the fundamental-matrix method if a purported transient state is absorbing itself?