From One-Step Blocks to Finite-Time Probabilities
For an absorbing Markov chain, the blocks \(Q\) and \(R\) describe what can happen on a single step from a transient state: the chain either remains among the transient states or enters an absorbing state. Matrix powers extend this one-step description to a specified number of steps. In particular, they answer two different questions: how much probability remains transient at time \(n\), and how much probability is absorbed at exactly step \(n\).
Let \((X_n)_{n\ge0}\) be a discrete-time Markov chain on a finite state space \(S=T\cup A\), defined on a probability space \((\Omega,\mathcal{F},\mathbb{P})\). Here \(T\) is the set of transient states and \(A\) is the set of absorbing states. A state \(a\in A\) is absorbing when \(p_{aa}=1\). Order the states with the transient states first and the absorbing states second. The transition matrix then has the block form
The matrix \(Q\) contains transition probabilities from \(T\) to \(T\), and \(R\) contains transition probabilities from \(T\) to \(A\). Each row of \(P\) sums to \(1\), so each row of \(Q\) plus the corresponding row of \(R\) sums to \(1\). The zero block and identity block express that an absorbing state cannot return to \(T\) or move to a different absorbing state.
The order of the factors matters: \(Q\) acts on transient-state probabilities before \(R\) takes them into the absorbing states. A row index in \(Q^{n-1}R\) specifies the starting transient state; a column index specifies the absorbing destination.
The Matrix-Power Formula
Consequently, starting from transient state \(i\), the probability of being in transient state \(j\) at time \(n\) is \((Q^n)_{ij}\). The probability of being absorbed in state \(a\) at exactly step \(n\) is \((Q^{n-1}R)_{ia}\), and the probability of having been absorbed by time \(n\) in state \(a\) is \(\left(\sum_{k=0}^{n-1}Q^kR\right)_{ia}\).
Proof. We prove the displayed block formula by induction on \(n\). For \(n=1\), its right-hand side is \(\begin{bmatrix}Q&R\\0&I\end{bmatrix}=P\), since the sum has the single term \(Q^0R=R\). Suppose the formula holds for some \(n\ge1\). Multiplying on the right by \(P\) gives
This is the formula for \(n+1\), proving the induction. The entries of \(P^n\) give the \(n\)-step transition probabilities by matrix multiplication, so its upper-left block gives the transient-to-transient probabilities and its upper-right block gives the absorbing-state probabilities by time \(n\). To isolate absorption exactly at step \(n\), subtract the absorbing block at time \(n-1\) from the one at time \(n\); the difference is \(Q^{n-1}R\). For \(n=1\), the absorbing block at time \(0\) is zero for a chain started in \(T\), and the difference is \(R=Q^0R\). \(\square\)
For an initial row distribution \(\alpha\) supported on \(T\), the transient-state distribution at time \(n\) is \(\alpha Q^n\). The row \(\alpha Q^{n-1}R\) gives the probabilities of absorption at exactly step \(n\), by destination. Summing these exact-step rows over \(1,\ldots,n\) gives the probability of absorption by time \(n\). These are finite-time formulas; they do not require a claim about what happens as \(n\) tends to infinity.
Proof. The block formula shows that the transient and absorbing parts of \(\alpha P^n\) are respectively \(\alpha Q^n\) and \(\alpha\sum_{k=0}^{n-1}Q^kR\). Since \(P\) is row-stochastic and \(\alpha\) is a probability row, \(\alpha P^n\) is also a probability row: multiplication by \(P\) preserves the row sum because \(P\mathbf{1}=\mathbf{1}\). Its transient and absorbing coordinates partition all states, so their sums add to \(1\). At \(n=0\), the chain starts in \(T\), and the transient mass is \(\alpha\mathbf{1}=1\), while the absorbed mass is \(0\). \(\square\)
Worked Calculations
Worked Example: Survival and Absorption by Step Three
Consider transient states \(1,2\) and absorbing states \(3,4\), with
The rows of \(P\) sum to \(1\): the first is \(\tfrac12+\tfrac14+\tfrac14=1\), the second is \(\tfrac12+\tfrac12=1\), and each absorbing row sums to \(1\). The row sums of \(Q\) are \(\tfrac34,\tfrac12\), and those of \(R\) are \(\tfrac14,\tfrac12\), respectively, so each transient row has total mass \(1\).
Squaring \(Q\) gives
For example, the upper-right entry of \(Q^2\) is \(\tfrac12\cdot\tfrac14+\tfrac14\cdot\tfrac12=\tfrac14\); the upper-right entry of \(Q^3=Q^2Q\) is \(\tfrac14\cdot\tfrac14+\tfrac14\cdot\tfrac12=\tfrac{3}{16}\). Starting from state \(1\), the probability of still being transient at time \(3\) is the first row sum of \(Q^3\), namely \(\tfrac18+\tfrac{3}{16}=\tfrac{5}{16}\).
Absorption exactly at step \(3\) is given by \(Q^2R\):
Thus, starting from state \(1\), the probability of absorption in state \(3\) at exactly step \(3\) is \(\tfrac{3}{16}\), and in state \(4\) it is \(0\). As a check of total mass by time \(3\), from state \(1\) the probabilities of absorption at steps \(1,2,3\) are \(\tfrac14,\tfrac14,\tfrac{3}{16}\). Their sum is \(\tfrac{11}{16}\), and adding the transient probability \(\tfrac{5}{16}\) gives \(1\).
Worked Example: Alternating Between Transient States
Let the transient states be \(1,2\) and the absorbing states \(3,4\), with
The first two rows of \(P\) sum to \(0+\tfrac12+\tfrac14+\tfrac14=1\) and \(\tfrac13+0+\tfrac13+\tfrac13=1\); the absorbing rows also sum to \(1\). The row sums of \(Q\) are \(\tfrac12,\tfrac13\), while those of \(R\) are \(\tfrac12,\tfrac23\), so the transient rows are valid probability distributions.
Starting at state \(1\), calculate absorption at exactly step \(3\). First,
The first row of \(Q^2R\) is the desired result: the probabilities of absorption in states \(3\) and \(4\) at step \(3\) are each \(\tfrac{1}{24}\). The probability of still being transient at time \(3\) is the first row sum of \(Q^3\). Multiplication gives \(Q^3=\begin{bmatrix}0&\tfrac{1}{12}\\\tfrac{1}{18}&0\end{bmatrix}\), so this probability is \(\tfrac{1}{12}\).
Check the mass by step: from state \(1\), absorption at step \(1\) has total probability \(\tfrac12\); at step \(2\), the first row of \(QR\) is \((\tfrac16,\tfrac16)\), with total \(\tfrac13\); and at step \(3\), the first row of \(Q^2R\) has total \(\tfrac1{12}\). The cumulative absorbed probability is \(\tfrac12+\tfrac13+\tfrac1{12}=\tfrac{11}{12}\). Adding the surviving probability \(\tfrac1{12}\) gives \(1\).
Worked Example: A Mixed Initial Distribution
Use transient states \(1,2\) and absorbing states \(3,4\), with
The rows of \(P\) sum to \(1\): the transient rows sum to \(\tfrac12+\tfrac14+\tfrac14=1\) and \(\tfrac13+\tfrac13+\tfrac13=1\), and the absorbing rows each sum to \(1\). Let the initial distribution be \(\mu=(\tfrac12,\tfrac14,\tfrac14,0)\). Its transient part is \(\alpha=(\tfrac12,\tfrac14)\), and its initial absorbing mass is \(\beta=(\tfrac14,0)\).
At time \(2\), the transient mass is \(\alpha Q^2\). Since \(Q^2=\begin{bmatrix}\tfrac14&0\\0&\tfrac19\end{bmatrix}\), this is \((\tfrac18,\tfrac1{36})\), with total \(\tfrac18+\tfrac1{36}=\tfrac{11}{72}\). Absorption exactly at step \(2\) is \(\alpha QR\). First \(\alpha Q=(\tfrac14,\tfrac1{12})\), so
For the full distribution at time \(2\), absorption already present at time \(0\) remains in place. The probability absorbed by step \(1\) from the initial transient mass is \(\alpha R=(\tfrac5{24},\tfrac5{24})\). Therefore the probabilities in states \(3,4\) at time \(2\) are respectively \(\tfrac14+\tfrac5{24}+\tfrac{13}{144}=\tfrac{79}{144}\) and \(0+\tfrac5{24}+\tfrac{13}{144}=\tfrac{43}{144}\). The total mass is \(\tfrac{79}{144}+\tfrac{43}{144}+\tfrac18+\tfrac1{36}=\tfrac{122}{144}+\tfrac{22}{144}=1\), as required.
Indexing Pitfall and Practical Checks
A frequent error is to use \(Q^nR\) for absorption at exactly step \(n\). That expression includes \(n\) transitions within \(T\) before entering \(A\), so it describes absorption at step \(n+1\). For example, in the first worked chain, starting from state \(1\), the probability of absorption in state \(3\) at step \(2\) is the first entry of the first row of \(QR\), which is \(\tfrac12\cdot\tfrac14+\tfrac14\cdot\tfrac12=\tfrac14\). Using \(Q^2R\) instead gives \(\tfrac{3}{16}\), the probability at step \(3\), not step \(2\). The correction is to use \(Q^{n-1}R\), with \(Q^0R=R\) at step \(1\).
Keep three quantities separate: \(Q^n\) gives the transient distribution at time \(n\); \(Q^{n-1}R\) gives absorption at exactly step \(n\); and \(\sum_{k=0}^{n-1}Q^kR\) gives absorption by time \(n\). When the chain can start in an absorbing state, include its initial mass separately in the cumulative absorbing distribution. As a final check, add transient and absorbing probabilities at the same time; their sum must be \(1\).
Check Your Understanding
Use the matrix-power formulas and verify each probability calculation by checking the corresponding row sums.
- For a chain started in a transient state, which matrix gives the transient-state distribution at time \(4\)?
- Which matrix gives the probabilities of absorption in each absorbing state at exactly step \(4\)?
- Why does \(Q^nR\) describe absorption one step later than \(Q^{n-1}R\)?
- In the mixed-initial-distribution example, what is the initial probability of already being in an absorbing state, and how is it included at time \(2\)?
- For any initial distribution supported on \(T\), state the finite-time mass check involving transient probability and cumulative absorption.