Deriving the Absorption Probability Formula

From Path Probabilities to the Absorption Matrix

An absorption probability can be computed by adding the probabilities of all paths that end in the relevant absorbing state. The paths have different lengths, but their probabilities have a common structure: first the chain makes some number of transitions among transient states, then it makes one final transition into an absorbing state. Matrix multiplication organizes the sum over paths of each fixed length. Summing over all possible lengths gives the absorption-probability formula $B=NR$.

Let $(X_n)_{n\ge0}$ be a discrete-time Markov chain on a probability space $(\Omega,\mathcal{F},\mathbb{P})$, with finite state space $S$ and row-stochastic transition matrix $P=(p_{ij})$. Suppose the states are ordered so the transient states come first and the absorbing states last. Write the canonical form as

P= \begin{bmatrix} Q&R\\ 0&I \end{bmatrix}.

Here $Q$ is the matrix of transition probabilities from transient states to transient states, and $R$ is the matrix of transition probabilities from transient states to absorbing states. An absorbing state remains fixed once reached. The rows of $P$ sum to one, so for each transient-state row the corresponding row sums of $Q$ and $R$ add to one. Let $r$ be the number of transient states and $a$ the number of absorbing states. The fundamental matrix is $N=\sum_{n=0}^{\infty}Q^n$, when this series converges. The entry $B_{i\ell}$ is the probability that a chain starting in transient state $i$ is eventually absorbed in absorbing state $\ell$.

Theorem (Absorption probability formula): Suppose the chain has finitely many transient states, absorbing states remain fixed, and absorption occurs with probability one from every transient state. Then $N=\sum_{n=0}^{\infty}Q^n$ exists entrywise, and the matrix of eventual absorption probabilities from transient states is $$ B=NR. $$ The term $Q^nR$ gives the probabilities of absorption after exactly $n$ transitions among transient states, followed by one transition into an absorbing state.

The condition that absorption occurs almost surely ensures that the infinite sum is meaningful and that its rows account for all possible absorption times. Here is a direct justification of convergence. From each transient state $i$, almost-sure absorption means that for some finite integer $m_i$, the probability of absorption by time $m_i$ is positive. Since there are finitely many transient states, choose $M=\max_i m_i$; the probability of absorption by time $M$ is then positive from every transient state. Let $\varepsilon$ be the minimum of those finitely many positive probabilities, so $\varepsilon>0$. Conditional on still being transient after each block of $M$ steps, the Markov property gives probability at most $1-\varepsilon$ of remaining transient for the next block. Thus the probability of remaining transient through $kM$ steps is at most $(1-\varepsilon)^k$. Consequently the row sums of $Q^n$ decay geometrically in blocks, and $\sum_{n\ge0}Q^n$ converges.

Proof. Fix transient state $i$, absorbing state $\ell$, and integer $n\ge0$. The event that the chain first enters an absorbing state at time $n+1$, and enters $\ell$, can be split according to the transient states visited at times $1,\ldots,n$. For any particular sequence $i_1,\ldots,i_n$ of transient states, its path probability is $p_{i i_1}p_{i_1 i_2}\cdots p_{i_{n-1}i_n}p_{i_n\ell}$. For $n=0$, the path has no intermediate transient state and its probability is simply $p_{i\ell}$. By the definition of matrix multiplication, summing these products over all transient-state sequences gives $(Q^nR)_{i\ell}$. The events indexed by $n$ are disjoint, since a path cannot first enter an absorbing state at two different times. Their union is the event of eventual absorption in $\ell$, because absorption occurs almost surely. Countable additivity therefore gives $B_{i\ell}=\sum_{n=0}^{\infty}(Q^nR)_{i\ell}$. This holds for every $i,\ell$, and hence $B=(\sum_{n=0}^{\infty}Q^n)R=NR$. $\square$

The index $n$ counts only transitions that remain within the transient states. The final transition into an absorbing state is represented by $R$, so it is not included in $n$. In particular, $n=0$ is not a zero-step absorption event: it means that the chain moves directly from its initial transient state into an absorbing state on its first transition. If the chain starts in an absorbing state, it is already absorbed; the corresponding probabilities are represented by the identity block in the canonical transition matrix, not by a row of $B$.

Worked Examples

Worked Example: A Two-State Transient Block

There are transient states $1,2$ and absorbing states $a,b$. From state $1$, the probabilities of moving to $1,2,a,b$ are respectively $\tfrac12,\tfrac14,\tfrac14,0$. From state $2$, the probabilities are $ \tfrac14,\tfrac12,0,\tfrac14$. Find the eventual absorption probabilities.

Each transient row sums to one: $\tfrac12+\tfrac14+\tfrac14+0=1$, and $\tfrac14+\tfrac12+0+\tfrac14=1$. The absorbing rows, in the order $a,b$, are $(1,0)$ and $(0,1)$, so they also sum to one. Thus

Q=\begin{bmatrix}\tfrac12&\tfrac14\\[2pt]\tfrac14&\tfrac12\end{bmatrix}, \qquad R=\begin{bmatrix}\tfrac14&0\\[2pt]0&\tfrac14\end{bmatrix}.

To calculate $N$, invert $I-Q$: $I-Q=\begin{bmatrix}\tfrac12&-\tfrac14\\-\tfrac14&\tfrac12\end{bmatrix}$. Its determinant is $\tfrac14-\tfrac1{16}=\tfrac3{16}$, so

N=(I-Q)^{-1} =\begin{bmatrix}\tfrac83&\tfrac43\\[2pt]\tfrac43&\tfrac83\end{bmatrix}, \qquad B=NR =\begin{bmatrix}\tfrac23&\tfrac13\\[2pt]\tfrac13&\tfrac23\end{bmatrix}.

Check: The first row of $B$ sums to $\tfrac23+\tfrac13=1$, and the second to $\tfrac13+\tfrac23=1$. Also, $B=R+QB$: its first row is $(\tfrac14,0)+\tfrac12(\tfrac23,\tfrac13)+\tfrac14(\tfrac13,\tfrac23)=(\tfrac23,\tfrac13)$, and its second row is $(0,\tfrac14)+\tfrac14(\tfrac23,\tfrac13)+\tfrac12(\tfrac13,\tfrac23)=(\tfrac13,\tfrac23)$. This independently checks the computed absorption probabilities.

Worked Example: A Three-State Cycle and the Final Transition

Consider transient states $1,2,3$ and absorbing states $a,b$. From $1$, the chain moves to $2$ or $a$, each with probability $\tfrac12$; from $2$, it moves to $3$ or $b$, each with probability $\tfrac12$; from $3$, it moves to $1$ or $a$, each with probability $\tfrac12$. Find the absorption probabilities from all three transient states.

Each transient row has two entries equal to $\tfrac12$, and therefore sums to one. The absorbing rows are $(1,0)$ and $(0,1)$, also with row sum one. In the order $1,2,3,a,b$, the blocks are

Q=\begin{bmatrix}0&\tfrac12&0\\0&0&\tfrac12\\\tfrac12&0&0\end{bmatrix}, \qquad R=\begin{bmatrix}\tfrac12&0\\0&\tfrac12\\\tfrac12&0\end{bmatrix}.

A complete cycle among transient states has probability $(\tfrac12)^3=\tfrac18$. Since $Q^3=\tfrac18 I$, summing the powers in groups of three gives $N=(I+Q+Q^2)(1+\tfrac18+\tfrac1{8^2}+\cdots)=\tfrac87(I+Q+Q^2)$. Here

I+Q+Q^2= \begin{bmatrix}1&\tfrac12&\tfrac14\\[2pt]\tfrac14&1&\tfrac12\\[2pt]\tfrac12&\tfrac14&1\end{bmatrix}, \qquad N= \begin{bmatrix}\tfrac87&\tfrac47&\tfrac27\\[2pt]\tfrac27&\tfrac87&\tfrac47\\[2pt]\tfrac47&\tfrac27&\tfrac87\end{bmatrix}.

Multiplication by $R$ gives

B=NR= \begin{bmatrix}\tfrac57&\tfrac27\\[2pt]\tfrac37&\tfrac47\\[2pt]\tfrac67&\tfrac17\end{bmatrix}.

Check: Each row sums to one: $\tfrac57+\tfrac27=1$, $\tfrac37+\tfrac47=1$, and $\tfrac67+\tfrac17=1$. For a path check from state $1$, immediate absorption in $a$ has probability $\tfrac12$. The path $1\to2\to3\to a$ has probability $\tfrac12\cdot\tfrac12\cdot\tfrac12=\tfrac18$, because it takes two transitions among transient states and then a third transition into $a$. The full probability of eventual absorption in $a$ is $\tfrac57$, which includes this path and paths that make any number of complete cycles first. In particular, the immediate path and this one path contribute $\tfrac12+\tfrac18=\tfrac58$; other paths contribute the remaining probability.

Worked Example: Summing a Geometric Path Series

There is one transient state $1$ and two absorbing states $a,b$. From $1$, the chain stays at $1$ with probability $\tfrac13$, moves to $a$ with probability $\tfrac13$, and moves to $b$ with probability $\tfrac13$. Find its absorption probabilities by summing path probabilities directly and by using $NR$.

The transient row sums to $\tfrac13+\tfrac13+\tfrac13=1$; each absorbing row has its single self-transition of probability $1$. Here $Q=[\tfrac13]$ and $R=[\tfrac13\ \ \tfrac13]$. Absorption in $a$ after exactly $n$ transitions among transient states has probability $(\tfrac13)^n\tfrac13$. Therefore its eventual probability is $\sum_{n=0}^{\infty}(\tfrac13)^n\tfrac13=\tfrac13\cdot\tfrac32=\tfrac12$. The same sum applies to $b$, so $B=[\tfrac12\ \ \tfrac12]$.

For the matrix calculation, $N=[\sum_{n=0}^{\infty}(\tfrac13)^n]=[\tfrac32]$, and $NR=[\tfrac32\cdot\tfrac13\ \ \tfrac32\cdot\tfrac13]=[\tfrac12\ \ \tfrac12]$. Check: the two absorption probabilities sum to $\tfrac12+\tfrac12=1$, and the direct path sum agrees with the matrix product.

Why the Rows Sum to One—and a Common Error

Under the theorem’s almost-sure absorption assumption, each row of $B$ must sum to one: eventual absorption occurs in one of the absorbing states. This also follows from the matrices. Since the transient rows of $P$ sum to one, $R\mathbf{1}=\mathbf{1}-Q\mathbf{1}$, where each $\mathbf{1}$ is an all-ones column vector of the appropriate size. For any integer $m\ge0$,

\sum_{n=0}^{m}Q^nR\mathbf{1} =\sum_{n=0}^{m}Q^n(\mathbf{1}-Q\mathbf{1}) =\mathbf{1}-Q^{m+1}\mathbf{1}.

The last term tends to zero because the probability of remaining transient tends to zero under almost-sure absorption. Taking $m$ to infinity gives $B\mathbf{1}=\mathbf{1}$.

Common mistake: counting the transient path but omitting its final transition. In the cycle example, reaching state $3$ by the path $1\to2\to3$ has probability $\tfrac12\cdot\tfrac12=\tfrac14$. That is not yet absorption in $a$: the chain must make one further transition, from $3$ to $a$, with probability $\tfrac12$. The probability of the full path $1\to2\to3\to a$ is therefore $\tfrac14\cdot\tfrac12=\tfrac18$, not $\tfrac14$. The factor $R$ supplies exactly this final transition. When reading $Q^nR$, count $n$ transient-to-transient transitions and then include the transition into the absorbing state.

If absorption is not almost sure, the same path sum still gives the probabilities of absorption in each absorbing state, but the rows of $B$ need not sum to one: some probability may belong to paths that remain transient forever. Thus the row-sum check is also a useful diagnostic. A row sum below one may signal either a genuine possibility of avoiding absorption or an error in the transition probabilities or calculations.

Check Your Understanding

For each question, keep the final transition into an absorbing state separate from the transitions counted by the exponent of $Q$.

In the product $Q^nR$, what does $n=0$ mean for a chain starting in a transient state?
For the path $1\to2\to3\to a$ in the three-state cycle example, calculate its probability and state how many transient-to-transient transitions it contains.
In the one-transient-state example, what is the probability of absorption in $b$ after exactly two transitions among transient states?
Why does almost-sure absorption imply that the rows of $B$ sum to one?
If a chain can remain transient forever with positive probability, what does a row sum below one in $B$ represent?

Deriving the Absorption Probability Formula

What You'll Learn