Tutorials › Stochastic Processes › Computing Absorption Probabilities with N and R

Home  /  Tutorials  /  Absorption, Hitting Times and First-Step Analysis

Absorption, Hitting Times and First-Step Analysis · Tutorial 242 of 994

Computing Absorption Probabilities with N and R

Compute exact absorption probabilities by forming the fundamental matrix \(N\), multiplying it by the absorption block \(R\), and applying the result to specified initial distributions.

Intermediate 11 min read

What You'll Learn

  • Identify the transient and absorbing blocks in canonical transition-matrix form.
  • Compute the fundamental matrix \(N=(I-Q)^{-1}\) and the absorption-probability matrix \(B=NR\).
  • Interpret each entry of \(B\) as the probability of a particular absorbing outcome.
  • Obtain outcome probabilities for a single initial state or a distribution over transient states.
  • Check exact matrix calculations using row sums and probability constraints.
  • Recognize why multiplying the blocks in the wrong order gives an invalid answer.

From Transient Visits to Absorption Outcomes

For a finite absorbing Markov chain, the transient states describe the possible steps before absorption, and the absorbing states record the eventual outcomes. The fundamental matrix \(N\) summarizes expected visits to transient states. To compute absorption probabilities, combine those expected visits with the one-step transitions from transient states into absorbing states. This tutorial focuses on that calculation: form \(B=NR\), interpret its entries, and use it to answer questions for specified initial states and distributions.

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

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

Here \(Q\) is the \(t\times t\) matrix of transitions among transient states, \(R\) is the \(t\times r\) matrix of transitions from transient to absorbing states, and \(I\) is the \(r\times r\) identity matrix. Each row of \(P\) must sum to \(1\); in particular, each row of \(Q\) and the corresponding row of \(R\) together sum to \(1\). Assume the chain is absorbed with probability \(1\) from each transient state, so that the fundamental matrix \(N=(I-Q)^{-1}\) exists. Its entry \(N_{ij}\) is the expected number of visits to transient state \(j\), counting time \(0\), when the chain starts in transient state \(i\).

Standard absorption-probability formula: For a finite absorbing chain with transient block \(Q\), absorbing block \(R\), and fundamental matrix \(N=(I-Q)^{-1}\), the matrix of eventual absorption probabilities is \(B=NR\). Thus \(B_{ik}\) is the probability that the chain is eventually absorbed in absorbing state \(k\), given that it starts in transient state \(i\). The derivation of this formula is given in the following treatment of the absorption-probability formula.

The order of multiplication follows from the roles and dimensions of the blocks: \(N\) is \(t\times t\) and \(R\) is \(t\times r\), so \(NR\) is \(t\times r\), with one row per transient starting state and one column per absorbing outcome. If the initial state is a particular transient state \(i\), use row \(i\) of \(B\). If the initial distribution over transient states is the row vector \(\alpha\), then the row vector of outcome probabilities is \(\alpha B\). The entries of \(\alpha\) must be nonnegative and sum to \(1\).

Why the Matrix Calculation Gives Probabilities

The formula is useful because it turns the problem into two exact matrix operations: compute \(N\), then multiply by \(R\). The following consequences also provide important checks on the result.

Proposition: If every transient state is eventually absorbed with probability \(1\), then every row of \(B=NR\) sums to \(1\). For any initial probability distribution \(\alpha\) on the transient states, \(\alpha B\) is a probability distribution over the absorbing outcomes.

Proof. Row-stochasticity of \(P\) gives \(Q\mathbf{1}+R\mathbf{1}=\mathbf{1}\), where each \(\mathbf{1}\) is an all-ones column vector of the required dimension. Therefore \(R\mathbf{1}=(I-Q)\mathbf{1}\). Using \(N=(I-Q)^{-1}\), we get \(B\mathbf{1}=NR\mathbf{1}=N(I-Q)\mathbf{1}=\mathbf{1}\). The entries of \(N\) are nonnegative because \(N=\sum_{n\ge0}Q^n\) for an absorbing chain, and the entries of \(R\) are nonnegative, so \(B\) has nonnegative entries. Thus each row of \(B\) is a probability distribution. If \(\alpha\) is a probability row vector, then \(\alpha B\) is nonnegative and its entries sum to \(\alpha B\mathbf{1}=\alpha\mathbf{1}=1\). \(\square\)

This proposition is both a mathematical consequence and a practical diagnostic. A negative entry, a row sum different from \(1\), or an initial-state outcome vector that does not sum to \(1\) indicates an error, unless the chain can avoid absorption with positive probability. The absorption assumption matters: if some transient states can avoid all absorbing states, the rows of \(B\) can sum to less than \(1\), because \(B\) records probabilities of eventual absorption in the listed absorbing states.

Worked Matrix Calculations

Worked Example: Two Transient States and Two Outcomes

Consider a chain on \(S=\{1,2,3,4\}\), at discrete times \(n\ge0\), on a probability space \((\Omega,\mathcal{F},\mathbb{P})\). States \(1,2\) are transient and states \(3,4\) are absorbing. In the order shown, let

$$ P= \begin{bmatrix} \tfrac12&\tfrac14&\tfrac14&0\\ \tfrac14&\tfrac12&0&\tfrac14\\ 0&0&1&0\\ 0&0&0&1 \end{bmatrix}. $$

Each transient row sums to \(\tfrac12+\tfrac14+\tfrac14=1\), and each absorbing row sums to \(1\). The blocks are \(Q=\begin{bmatrix}\tfrac12&\tfrac14\\\tfrac14&\tfrac12\end{bmatrix}\) and \(R=\begin{bmatrix}\tfrac14&0\\0&\tfrac14\end{bmatrix}\). First compute

$$ I-Q= \begin{bmatrix} \tfrac12&-\tfrac14\\ -\tfrac14&\tfrac12 \end{bmatrix}, \qquad \det(I-Q)=\tfrac12\cdot\tfrac12-\left(-\tfrac14\right)\left(-\tfrac14\right) =\tfrac14-\tfrac1{16}=\tfrac3{16}. $$

For a \(2\times2\) matrix, invert by swapping the diagonal entries, changing the signs of the off-diagonal entries, and dividing by the determinant. This gives

$$ N=(I-Q)^{-1} = \begin{bmatrix} \tfrac83&\tfrac43\\ \tfrac43&\tfrac83 \end{bmatrix}. $$

Now multiply \(N\) by \(R\), keeping the absorbing outcomes in the column order \(3,4\):

$$ B=NR= \begin{bmatrix} \tfrac83&\tfrac43\\ \tfrac43&\tfrac83 \end{bmatrix} \begin{bmatrix} \tfrac14&0\\ 0&\tfrac14 \end{bmatrix} = \begin{bmatrix} \tfrac23&\tfrac13\\ \tfrac13&\tfrac23 \end{bmatrix}. $$

Starting from state \(1\), the probability of absorption in state \(3\) is \(\tfrac23\), and the probability of absorption in state \(4\) is \(\tfrac13\). From state \(2\), those probabilities are \(\tfrac13\) and \(\tfrac23\). Check: the first row sums to \(\tfrac23+\tfrac13=1\), and the second sums to \(\tfrac13+\tfrac23=1\), as required when absorption occurs almost surely.

Worked Example: A Nonuniform Initial Distribution

Use the chain and matrix \(B\) from the preceding example, but suppose the initial state is \(1\) with probability \(\tfrac34\) and state \(2\) with probability \(\tfrac14\). The initial row vector over transient states is \(\alpha=(\tfrac34,\tfrac14)\). Multiply it by \(B\):

$$ \alpha B = \begin{bmatrix}\tfrac34&\tfrac14\end{bmatrix} \begin{bmatrix}\tfrac23&\tfrac13\\\tfrac13&\tfrac23\end{bmatrix} = \begin{bmatrix} \tfrac34\cdot\tfrac23+\tfrac14\cdot\tfrac13& \tfrac34\cdot\tfrac13+\tfrac14\cdot\tfrac23 \end{bmatrix} = \begin{bmatrix}\tfrac7{12}&\tfrac5{12}\end{bmatrix}. $$

For the first entry, \(\tfrac34\cdot\tfrac23=\tfrac12=\tfrac6{12}\) and \(\tfrac14\cdot\tfrac13=\tfrac1{12}\), giving \(\tfrac7{12}\). For the second, \(\tfrac34\cdot\tfrac13=\tfrac14=\tfrac3{12}\) and \(\tfrac14\cdot\tfrac23=\tfrac16=\tfrac2{12}\), giving \(\tfrac5{12}\). Thus the eventual absorption probabilities in states \(3\) and \(4\) are \(\tfrac7{12}\) and \(\tfrac5{12}\), respectively. Check: \(\tfrac7{12}+\tfrac5{12}=1\). The same result follows by weighting the state-specific probabilities: \(\tfrac34\cdot\tfrac23+\tfrac14\cdot\tfrac13=\tfrac7{12}\) for state \(3\), and \(\tfrac34\cdot\tfrac13+\tfrac14\cdot\tfrac23=\tfrac5{12}\) for state \(4\).

Worked Example: Three Transient States

Let \((X_n)_{n\ge0}\) be a discrete-time chain on \(S=\{1,2,3,4,5\}\), with transient states \(1,2,3\) and absorbing outcomes \(4,5\). Its transition matrix is

$$ P= \begin{bmatrix} \tfrac12&\tfrac14&0&\tfrac14&0\\ 0&0&\tfrac12&0&\tfrac12\\ 0&0&\tfrac12&\tfrac14&\tfrac14\\ 0&0&0&1&0\\ 0&0&0&0&1 \end{bmatrix}. $$

The transient rows sum to \(\tfrac12+\tfrac14+\tfrac14=1\), \(0+0+\tfrac12+0+\tfrac12=1\), and \(0+0+\tfrac12+\tfrac14+\tfrac14=1\); the absorbing rows each sum to \(1\). Thus

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

Here \(I-Q=\begin{bmatrix}\tfrac12&-\tfrac14&0\\0&1&-\tfrac12\\0&0&\tfrac12\end{bmatrix}\). Inverting this upper-triangular matrix gives

$$ N= \begin{bmatrix} 2&\tfrac12&\tfrac12\\ 0&1&1\\ 0&0&2 \end{bmatrix}. $$

For a direct check, multiplication gives \((I-Q)N=I\): the first row of the product is \((1,\tfrac14-\tfrac14,0)=(1,0,0)\); the second is \((0,1,1-1)=(0,1,0)\); and the third is \((0,0,1)\). Now

$$ B=NR= \begin{bmatrix} 2&\tfrac12&\tfrac12\\ 0&1&1\\ 0&0&2 \end{bmatrix} \begin{bmatrix} \tfrac14&0\\ 0&\tfrac12\\ \tfrac14&\tfrac14 \end{bmatrix} = \begin{bmatrix} \tfrac58&\tfrac38\\ \tfrac14&\tfrac34\\ \tfrac12&\tfrac12 \end{bmatrix}. $$

For example, the first row is \((2\cdot\tfrac14+\tfrac12\cdot0+\tfrac12\cdot\tfrac14,\ 2\cdot0+\tfrac12\cdot\tfrac12+\tfrac12\cdot\tfrac14)=(\tfrac12+\tfrac18,\tfrac14+\tfrac18)=(\tfrac58,\tfrac38)\). The second row is \((0+\tfrac14,\ 0+\tfrac12+\tfrac14)=(\tfrac14,\tfrac34)\), and the third is \((2\cdot\tfrac14,2\cdot\tfrac14)=(\tfrac12,\tfrac12)\). Check: the three row sums are \(\tfrac58+\tfrac38=1\), \(\tfrac14+\tfrac34=1\), and \(\tfrac12+\tfrac12=1\). Starting in state \(2\), absorption in state \(5\) is three times as likely as absorption in state \(4\), since \(\tfrac34=3\cdot\tfrac14\).

Common Mistakes and Useful Checks

A frequent error is to multiply the blocks in the wrong order. In the first example, \(QR\) is dimensionally possible, but it is not the absorption-probability matrix. The actual multiplication is

$$ QR= \begin{bmatrix} \tfrac12&\tfrac14\\ \tfrac14&\tfrac12 \end{bmatrix} \begin{bmatrix} \tfrac14&0\\ 0&\tfrac14 \end{bmatrix} = \begin{bmatrix} \tfrac18&\tfrac1{16}\\ \tfrac1{16}&\tfrac18 \end{bmatrix}. $$

Its first row sums to \(\tfrac18+\tfrac1{16}=\tfrac3{16}\), not \(1\), so it cannot give the eventual outcome probabilities in this chain. The correction is to compute \(N=(I-Q)^{-1}\) first and then use \(NR\), as the formula requires. Another error is to treat a distribution over initial transient states as a column vector and multiply it on the left. With the row-vector convention, the correct expression is \(\alpha B\); it returns one probability for each absorbing outcome.

Before interpreting a result, check that the states are ordered consistently in \(Q\), \(R\), \(N\), and \(B\); verify every row of the original \(P\) sums to \(1\); and confirm the dimensions \(N:t\times t\), \(R:t\times r\), and \(B:t\times r\). When absorption is certain, each row of \(B\) must sum to \(1\). For an initial distribution \(\alpha\), also check that its entries sum to \(1\) and that the entries of \(\alpha B\) sum to \(1\). These checks detect many arithmetic and indexing errors before the probabilities are used.

Check Your Understanding

In each question, keep transient states in the row-vector convention and absorbing outcomes in the column order given.

  1. If \(N\) is \(3\times3\) and \(R\) is \(3\times2\), what are the dimensions and interpretation of \(B=NR\)?
  2. For the three-transient-state example, what are the probabilities of absorption in state \(4\) and state \(5\) when the chain starts in state \(3\)? Verify that they sum to \(1\).
  3. For the first example, compute the outcome probabilities from initial distribution \(\alpha=(\tfrac12,\tfrac12)\) using \(\alpha B\).
  4. Why does a row sum of \(1\) in \(B\) provide a useful check when absorption occurs almost surely?
  5. In a finite chain where absorption is not certain, why might a row of \(B\) sum to less than \(1\)?

Previous

Next

Back to Tutorials