From Transitions to Expected Visits
An absorbing Markov chain has states that, once reached, cannot be left. These states can represent outcomes such as completion, failure, or an absorbing endpoint in a network process. The other states are transient: a chain starting there eventually reaches an absorbing state. A transition matrix describes the probability of moving in one step; its block structure lets us calculate not only where the chain may go next, but how often it visits transient states before it is absorbed.
We use column state vectors. Thus the entry in column \(j\), row \(i\) of a transition matrix is the probability of moving from state \(j\) to state \(i\), and each column sums to \(1\). If \(\mathbf{x}_k\) is the column vector of state probabilities at time \(k\), then \(\mathbf{x}_{k+1}=\mathbf{P}\mathbf{x}_k\). Repeated multiplication gives \(\mathbf{x}_k=\mathbf{P}^k\mathbf{x}_0\). The results below concern a finite chain with at least one absorbing state, where every other state is eventually absorbed with probability \(1\).
Suppose there are \(t\) transient states and \(a\) absorbing states. Then \(\mathbf{Q}\in\mathbb{R}^{t\times t}\), \(\mathbf{R}\in\mathbb{R}^{a\times t}\), and the identity block is \(\mathbf{I}_a\). Because the columns of \(\mathbf{P}\) sum to \(1\), each column of \(\mathbf{Q}\) has sum at most \(1\); any missing probability in that column is in \(\mathbf{R}\). The matrix \(\mathbf{Q}^k\) tracks paths that have stayed among the transient states for \(k\) steps.
The Fundamental Matrix
This definition requires \(\mathbf{I}_t-\mathbf{Q}\) to be invertible. The following result proves that it is invertible under the stated absorption assumption, and explains the entries of \(\mathbf{N}\).
Proof. Starting from any transient state \(j\), absorption eventually occurs with probability \(1\). Therefore there is a finite number \(n_j\) such that the probability of being absorbed by step \(n_j\) is positive. There are finitely many transient states, so let \(m\) be the largest of these \(n_j\), and let \(\varepsilon\) be the smallest of their positive probabilities of absorption by their respective \(n_j\). Then \(m\geq 1\) and \(\varepsilon>0\). Absorption by step \(n_j\) implies absorption by step \(m\), so from each transient state the probability of still being transient after \(m\) steps is at most \(1-\varepsilon\). Hence every column sum of the nonnegative matrix \(\mathbf{Q}^m\) is at most \(1-\varepsilon\). Since every column sum of \(\mathbf{Q}^r\) is at most \(1\) for \(r\geq 0\), successive blocks of \(m\) steps show that every column sum of \(\mathbf{Q}^{qm+r}\) is at most \((1-\varepsilon)^q\), for integers \(q\geq0\) and \(0\leq r<m\). It follows that \(\mathbf{Q}^k\) tends entrywise to \(\mathbf{O}\), and that the series \(\sum_{k=0}^{\infty}\mathbf{Q}^k\) converges entrywise.
For every integer \(s\geq0\), multiplying out the finite geometric sum gives $$ (\mathbf{I}_t-\mathbf{Q})(\mathbf{I}_t+\mathbf{Q}+\cdots+\mathbf{Q}^s) =\mathbf{I}_t-\mathbf{Q}^{s+1}. $$ The same identity holds with the factors reversed, because powers of \(\mathbf{Q}\) commute with \(\mathbf{Q}\). Letting \(s\) tend to infinity makes the right-hand side tend to \(\mathbf{I}_t\). Thus the sum is a left and right inverse of \(\mathbf{I}_t-\mathbf{Q}\), so it equals \((\mathbf{I}_t-\mathbf{Q})^{-1}\). At time \(k\), the transient-state probability vector is \(\mathbf{Q}^k\mathbf{x}_0\). Its \(i\)-th entry is the probability of being in transient state \(i\) at time \(k\). The expected number of visits to state \(i\) is the sum, over \(k\geq0\), of these probabilities. Summing the vectors gives \(\sum_{k=0}^{\infty}\mathbf{Q}^k\mathbf{x}_0=\mathbf{N}\mathbf{x}_0\), as claimed. \(\square\)
In particular, the \(i,j\) entry of \(\mathbf{N}\) is the expected number of visits to transient state \(i\) when the chain starts in transient state \(j\). A starting probability vector can mix several initial states: multiplying by \(\mathbf{N}\) takes the corresponding weighted average of those expected visits.
Calculating Expected Visits
Worked Example: Visits Before Reaching One Absorbing State
Consider transient states \(T_1,T_2\) and absorbing state \(A\). From \(T_1\), the chain stays in \(T_1\) with probability \(\tfrac12\), moves to \(T_2\) with probability \(\tfrac14\), and moves to \(A\) with probability \(\tfrac14\). From \(T_2\), it stays in \(T_2\) with probability \(\tfrac12\) and moves to \(A\) with probability \(\tfrac12\). Starting at \(T_1\), find the expected visits to the transient states.
Ordering the states as \(T_1,T_2,A\), the column-state transition matrix and its transient blocks are
Compute the inverse of \(\mathbf{I}_2-\mathbf{Q}\):
To check the inverse, multiply in both orders:
The initial vector for starting at \(T_1\) is \(\mathbf{x}_0=(1,0)^{\top}\). Therefore \(\mathbf{N}\mathbf{x}_0=(2,1)^{\top}\): the expected visits are \(2\) to \(T_1\) and \(1\) to \(T_2\). The absorption probability is also checked directly: $$ \mathbf{R}\mathbf{N}\mathbf{x}_0 = \begin{bmatrix}\frac14&\frac12\end{bmatrix} \begin{bmatrix}2\\1\end{bmatrix} =\frac12+\frac12=1. $$ The probabilities of all possible absorbing outcomes sum to \(1\), as required.
Absorption Probabilities
The same blocks also give the distribution of the eventual absorbing state. If the chain is transient at time \(k\), the vector of probabilities of moving into absorbing states on the next step is \(\mathbf{R}\mathbf{Q}^k\mathbf{x}_0\). Summing over all possible times gives the following result.
Proof. For each \(k\geq0\), \(\mathbf{Q}^k\mathbf{x}_0\) gives the probabilities of being in each transient state at time \(k\) without having been absorbed. Multiplication by \(\mathbf{R}\) gives the probabilities of moving from those states into each absorbing state on the next step. Absorption on different steps gives disjoint outcomes, so the probability of absorption in each absorbing state is the sum over \(k\geq0\) of these vectors. By the fundamental-matrix theorem, that sum is \(\sum_{k=0}^{\infty}\mathbf{R}\mathbf{Q}^k\mathbf{x}_0=\mathbf{R}\mathbf{N}\mathbf{x}_0\). \(\square\)
For a probability vector \(\mathbf{x}_0\) whose entries sum to \(1\), the entries of \(\mathbf{R}\mathbf{N}\mathbf{x}_0\) also sum to \(1\). Indeed, let \(\mathbf{1}_t^{\top}\) and \(\mathbf{1}_a^{\top}\) denote row vectors of ones of the indicated sizes. The column sums of \(\mathbf{P}\) give \(\mathbf{1}_a^{\top}\mathbf{R}=\mathbf{1}_t^{\top}(\mathbf{I}_t-\mathbf{Q})\). Therefore $$ \mathbf{1}_a^{\top}\mathbf{R}\mathbf{N}\mathbf{x}_0 = \mathbf{1}_t^{\top}(\mathbf{I}_t-\mathbf{Q})\mathbf{N}\mathbf{x}_0 = \mathbf{1}_t^{\top}\mathbf{x}_0 =1. $$ This check confirms that the computed probabilities account for all eventual outcomes.
Worked Example: Visits and Two Absorbing Outcomes
Suppose there are transient states \(T_1,T_2\) and absorbing states \(A_1,A_2\). From either transient state, the chain stays in that state with probability \(\tfrac12\), moves to the other transient state with probability \(\tfrac14\), and moves to its corresponding absorbing state with probability \(\tfrac14\): from \(T_1\) to \(A_1\), and from \(T_2\) to \(A_2\). Starting with equal probabilities in \(T_1\) and \(T_2\), find the expected visits and absorption probabilities.
With the state order \(T_1,T_2,A_1,A_2\), the blocks are
Since \(\mathbf{I}_2-\mathbf{Q}=\begin{bmatrix}\frac12&-\frac14\\-\frac14&\frac12\end{bmatrix}\), its inverse is \(\mathbf{N}=\begin{bmatrix}\frac83&\frac43\\\frac43&\frac83\end{bmatrix}\). Checking the product gives
The expected-visit vector is $$ \mathbf{N}\mathbf{x}_0 = \begin{bmatrix} \frac43+\frac23\\ \frac23+\frac43 \end{bmatrix} = \begin{bmatrix}2\\2\end{bmatrix}. $$ Thus the expected number of visits is \(2\) to each transient state. The eventual absorption probabilities are $$ \mathbf{R}\mathbf{N}\mathbf{x}_0 = \begin{bmatrix} \frac14&0\\ 0&\frac14 \end{bmatrix} \begin{bmatrix}2\\2\end{bmatrix} = \begin{bmatrix}\frac12\\\frac12\end{bmatrix}. $$ They are nonnegative and sum to \(1\).
A Second Visit Calculation
Worked Example: Alternating Between Transient States
There are two transient states \(T_1,T_2\) and one absorbing state \(A\). From either transient state, the chain moves to the other transient state with probability \(\tfrac12\) and to \(A\) with probability \(\tfrac12\). Starting at \(T_1\), calculate the expected visits to each transient state and the probability of absorption.
Here \(\mathbf{Q}=\begin{bmatrix}0&\frac12\\\frac12&0\end{bmatrix}\) and \(\mathbf{R}=\begin{bmatrix}\frac12&\frac12\end{bmatrix}\). Hence \(\mathbf{I}_2-\mathbf{Q}=\begin{bmatrix}1&-\frac12\\-\frac12&1\end{bmatrix}\), with inverse \(\mathbf{N}=\begin{bmatrix}\frac43&\frac23\\\frac23&\frac43\end{bmatrix}\). Direct multiplication verifies the inverse:
For \(\mathbf{x}_0=(1,0)^{\top}\), the expected visits are \(\mathbf{N}\mathbf{x}_0=(\frac43,\frac23)^{\top}\). The absorption probability is $$ \mathbf{R}\mathbf{N}\mathbf{x}_0 = \begin{bmatrix}\frac12&\frac12\end{bmatrix} \begin{bmatrix}\frac43\\\frac23\end{bmatrix} = \frac23+\frac13=1. $$ The expected total number of visits to transient states is \(\frac43+\frac23=2\), including the starting visit.
Counting Time Zero Correctly
The entry \(\mathbf{N}\mathbf{x}_0\) counts visits at times \(0,1,2,\ldots\) while the chain remains transient. In particular, if the chain starts at \(T_1\), the time-zero visit to \(T_1\) is included. This also explains why the expected total number of transient visits equals the expected number of steps until absorption when the chain starts transient: a path absorbed after \(r\) transitions has exactly \(r\) transient visits, at times \(0\) through \(r-1\).
Common mistake: omitting the initial visit. In the alternating-states example, a tempting but incorrect calculation is to subtract the identity and report \((\mathbf{N}-\mathbf{I}_2)\mathbf{x}_0=(\frac13,\frac23)^{\top}\) as the expected visits before absorption. This omits the visit to \(T_1\) at time \(0\), and so cannot be the requested total. The correct total is \(\mathbf{N}\mathbf{x}_0=(\frac43,\frac23)^{\top}\). Subtracting the identity is appropriate only when the question explicitly asks for visits after time \(0\); for this example, the future visits are \((\frac13,\frac23)^{\top}\), while the initial visit adds \((1,0)^{\top}\).
Keep the state-vector convention consistent throughout: with column state vectors, transitions from transient states to absorbing states appear in the lower-left block \(\mathbf{R}\), and the absorption probabilities are \(\mathbf{R}\mathbf{N}\mathbf{x}_0\), in that order. The expected visits are found from \(\mathbf{N}\mathbf{x}_0\); the absorption calculation then applies \(\mathbf{R}\) to those transient visits.
Check Your Understanding
Use the column-state convention and count the time-zero visit when the chain starts in a transient state.
- In block form, what do \(\mathbf{Q}\) and \(\mathbf{R}\) represent?
- For \(\mathbf{Q}=\begin{bmatrix}\frac12&0\\\frac14&\frac12\end{bmatrix}\), calculate \((\mathbf{I}_2-\mathbf{Q})^{-1}\).
- If \(\mathbf{N}=\begin{bmatrix}2&0\\1&2\end{bmatrix}\) and the chain starts at the first transient state, what are the expected visits to the two transient states?
- Given \(\mathbf{R}=\begin{bmatrix}\frac14&\frac12\end{bmatrix}\) and \(\mathbf{N}\mathbf{x}_0=(2,1)^{\top}\), calculate the absorption probability.
- In one sentence, explain why \(\mathbf{N}\mathbf{x}_0\) includes the starting visit.
