Canonical Form of a Finite Absorbing Chain

Why Put a Chain in Canonical Form?

When a Markov chain has absorbing states, arranging its states in a suitable order reveals its structure directly in the transition matrix. The resulting canonical form separates transitions among transient states from transitions into absorbing states. This is a bookkeeping step, not a new transition rule: it changes the order in which states are listed, while leaving the chain itself unchanged.

Throughout, let $(X_n)_{n\ge 0}$ be a discrete-time Markov chain on a finite state space $S$, defined on a probability space $(\Omega,\mathcal{F},\mathbb{P})$. Its transition matrix is $P=(p_{ij})$, where $p_{ij}=\mathbb{P}(X_{n+1}=j\mid X_n=i)$; each row sums to $1$. A state $a$ is absorbing if $p_{aa}=1$. In a finite absorbing chain, the set $A$ of absorbing states is nonempty, and every state outside $A$ has a finite path of positive-probability transitions to some state in $A$. Write $T=S\setminus A$ for the remaining states. Under this reachability condition, those remaining states are transient: the chain eventually reaches $A$ with probability $1$, as shown below.

Definition (Canonical form): List the states of $T$ first and the states of $A$ second, and use that same order for the rows and columns of $P$. The transition matrix then has the block form $$ P=\begin{bmatrix}Q&R\\0&I\end{bmatrix}. $$ Here $Q$ records transitions from $T$ to $T$, $R$ records transitions from $T$ to $A$, the zero block records that absorbing states cannot move to $T$, and $I$ records that each absorbing state stays in itself.

The letters $Q$ and $R$ name the two blocks in the top row. The purpose here is to recognize the form and interpret its entries. The row-sum rule for $P$ implies that each row of $Q$, together with the corresponding row of $R$, sums to $1$. The lower block rows sum to $1$ because they are rows of the identity matrix.

Why the Reordering Gives This Form

Theorem (Canonical block form): Suppose $P$ is the transition matrix of a finite Markov chain, $A$ is a nonempty set of absorbing states, and every state outside $A$ has a positive-probability path to $A$. After listing the states outside $A$ first and the states in $A$ second, the matrix has canonical form. Moreover, absorption occurs eventually with probability $1$ from every starting state.

Proof. Let $T=S\setminus A$, and list the states in the order $T,A$. For $i\in A$, absorption means $p_{ii}=1$. Since row $i$ sums to $1$ and its entries are nonnegative, $p_{ij}=0$ for every $j\ne i$. Thus a row indexed by a state in $A$ has zeros in the columns for $T$, and within the columns for $A$ it has a $1$ at its own state and zeros elsewhere. These rows form the lower blocks $0$ and $I$. The remaining rows and columns form blocks $Q$ and $R$, giving the displayed form. For a row indexed by $i\in T$, the original row-sum condition gives $\sum_{j\in T}p_{ij}+\sum_{a\in A}p_{ia}=1$, which is exactly the row-sum condition across its $Q$ and $R$ blocks.

It remains to verify eventual absorption. For each $i\in T$, choose a finite path from $i$ to $A$ whose transition probabilities are all positive. Let its length be $m_i$ and its path probability be $c_i>0$, the product of those transition probabilities. Since $T$ is finite, if it is nonempty we can take $N=\max_{i\in T}m_i$ and $\delta=\min_{i\in T}c_i>0$. Starting from any state in $T$, the probability of reaching $A$ within $N$ steps is at least $\delta$. The Markov property then gives, for each integer $k\ge 0$, $\mathbb{P}_i(T_A>kN)\le (1-\delta)^k$, where $T_A=\inf\{n\ge0:X_n\in A\}$. This bound tends to $0$, so $\mathbb{P}_i(T_A=\infty)=0$. If $T$ is empty, the chain starts in $A$ from every state and absorption is immediate. Thus absorption occurs almost surely in all cases. $\square$

The hypothesis about paths is important for the absorption conclusion, but not for the mechanical block arrangement. If a set of states is absorbing, placing those states last produces the same lower blocks even if some other states can never reach them. The next examples separate these two facts.

Worked Example: Reordering an Interleaved State List

Let the original state order be $(a,c,b,d)$. States $c$ and $d$ are absorbing. From $a$, the chain moves to $b$ or $c$, each with probability $\tfrac12$. From $b$, it moves to $a$ with probability $\tfrac13$ and to $d$ with probability $\tfrac23$. The original transition matrix, in the stated order, is

P= \begin{bmatrix} 0&\tfrac12&\tfrac12&0\\ 0&1&0&0\\ \tfrac13&0&0&\tfrac23\\ 0&0&0&1 \end{bmatrix}.

Check each row before rearranging: the row sums are $0+\tfrac12+\tfrac12+0=1$, $0+1+0+0=1$, $\tfrac13+0+0+\tfrac23=1$, and $0+0+0+1=1$. The states outside $A=\{c,d\}$ are $T=\{a,b\}$. Both have a positive-probability path to $A$: from $a$ there is a direct transition to $c$, and from $b$ there is a direct transition to $d$.

Use the new order $(a,b,c,d)$, moving the row and column for $b$ ahead of those for $c$. The reordered matrix is

P= \begin{bmatrix} 0&\tfrac12&\tfrac12&0\\ \tfrac13&0&0&\tfrac23\\ 0&0&1&0\\ 0&0&0&1 \end{bmatrix} = \begin{bmatrix} Q&R\\ 0&I \end{bmatrix}, \qquad Q=\begin{bmatrix}0&\tfrac12\\\tfrac13&0\end{bmatrix}, \quad R=\begin{bmatrix}\tfrac12&0\\0&\tfrac23\end{bmatrix}.

The top-left block records moves between $a$ and $b$; the top-right block records moves from those states into $c$ and $d$. The bottom blocks express that $c$ and $d$ stay where they are. As a check, the first reordered row sums to $0+\tfrac12+\tfrac12+0=1$, the second to $\tfrac13+0+0+\tfrac23=1$, and the last two each sum to $1$. The block row sums also check: the two $Q$-row sums are $\tfrac12$ and $\tfrac13$, while the corresponding $R$-row sums are $\tfrac12$ and $\tfrac23$, giving $1$ in each case.

Reading the Blocks and Their Constraints

For a chain with $r$ states outside $A$ and $s$ absorbing states, the blocks have sizes $r$ by $r$ for $Q$, $r$ by $s$ for $R$, $s$ by $r$ for the zero block, and $s$ by $s$ for $I$. These dimensions follow from the order of the rows and columns: the first $r$ rows and columns correspond to $T$, and the last $s$ correspond to $A$.

For a state $i\in T$, the sum of row $i$ in $Q$ is the one-step probability of remaining in $T$, and the sum of row $i$ in $R$ is the one-step probability of entering $A$. Those two probabilities add to $1$. Individual entries of $R$ distinguish which absorbing state is reached in one step. In contrast, each row of the bottom blocks has its single $1$ at the column of the same absorbing state. In particular, the bottom-right block is an identity matrix, not a matrix whose rows can move among absorbing states.

Worked Example: Identifying Each Block

Consider states $(u,\alpha,v,\beta)$, where $\alpha$ and $\beta$ are absorbing. From $u$, the chain moves to $u,\alpha,v$ with probabilities $\tfrac12,\tfrac14,\tfrac14$, respectively. From $v$, it moves to $u$ with probability $\tfrac13$ and to $\beta$ with probability $\tfrac23$. The transition matrix in the original order is

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

The row sums are $\tfrac12+\tfrac14+\tfrac14+0=1$, $0+1+0+0=1$, $\tfrac13+0+0+\tfrac23=1$, and $0+0+0+1=1$. The transient states are $u,v$, and each has a positive-probability path to an absorbing state. Reorder to $(u,v,\alpha,\beta)$. The resulting matrix and blocks are

P= \begin{bmatrix} \tfrac12&\tfrac14&\tfrac14&0\\ \tfrac13&0&0&\tfrac23\\ 0&0&1&0\\ 0&0&0&1 \end{bmatrix} = \begin{bmatrix} Q&R\\ 0&I \end{bmatrix}, \qquad Q=\begin{bmatrix}\tfrac12&\tfrac14\\\tfrac13&0\end{bmatrix}, \quad R=\begin{bmatrix}\tfrac14&0\\0&\tfrac23\end{bmatrix}.

Here $Q$ records the transitions $u\to u$, $u\to v$, and $v\to u$; its row sums are $\tfrac12+\tfrac14=\tfrac34$ and $\tfrac13+0=\tfrac13$. The $R$-row sums are $\tfrac14+0=\tfrac14$ and $0+\tfrac23=\tfrac23$. Adding the corresponding row sums gives $\tfrac34+\tfrac14=1$ and $\tfrac13+\tfrac23=1$. Thus the first transient state has probability $\tfrac14$ of absorption in one step, while the second has probability $\tfrac23$. Those are one-step probabilities, not by themselves the probabilities of eventual absorption in each state.

The row-sum relationship can also be read in reverse. If a row-stochastic matrix is displayed in the pattern $\begin{bmatrix}Q&R\\0&I\end{bmatrix}$, its last states are absorbing: each of the last rows has probability $1$ of staying at its own state. The pattern therefore identifies absorbing states, while reachability from the other states is a separate property.

What the Pattern Does Not Prove

Worked Example: Canonical Form Without Eventual Absorption

Consider $S=\{1,2,3\}$ with $A=\{3\}$ and

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

Every row sums to $1$: the sums are $0+1+0=1$, $1+0+0=1$, and $0+0+1=1$. State $3$ is absorbing, and states $1,2$ are already listed before it, so the matrix has canonical block form with $Q=\begin{bmatrix}0&1\\1&0\end{bmatrix}$, $R=\begin{bmatrix}0\\0\end{bmatrix}$, lower-left block $\begin{bmatrix}0&0\end{bmatrix}$, and lower-right block $[1]$. But from state $1$ the chain alternates between $1$ and $2$; from state $2$ it alternates between $2$ and $1$. Neither path reaches $3$. The block pattern holds, but the reachability assumption fails, and absorption does not occur from states $1$ or $2$.

Common mistake. In the preceding example with states $u,v,\alpha,\beta$, one might look at the first row of $R$, add its entries to get $\tfrac14$, and call that the probability of eventual absorption starting from $u$. That calculation gives only the probability of entering $A$ on the very next step. Indeed, the first row of $Q$ sums to $\tfrac34$, so the remaining probability is a transition to $u$ or $v$, not a failure to ever be absorbed. The correction is to describe $\tfrac14$ as the one-step absorption probability; an eventual absorption probability requires accounting for what happens after transitions within $T$.

There is one harmless boundary case: if every state is absorbing, then $T$ is empty and the whole matrix is $I$. There are no $Q$ or $R$ entries to interpret, and the chain is already absorbed at time $0$ from any initial state. The convention still describes the structure, with empty top blocks.

Takeaway: Canonical form is obtained by applying the same state reordering to rows and columns. It exposes transitions within the nonabsorbing states and transitions from them into absorbing states, while the lower block rows are forced by absorption. The form alone does not establish that every starting state can reach the absorbing set.

Check Your Understanding

Use the definitions and row-sum checks above to test your understanding of the block form.

For $S=\{a,b,c\}$, suppose $c$ is absorbing and the original order is $(a,c,b)$. Which state order puts the matrix in canonical form?
In canonical form, what does the sum of a row of $R$ represent? How does it relate to the corresponding row sum of $Q$?
Why must the lower-right block be an identity matrix when the listed states are absorbing states?
In the three-state example with states $1,2,3$, identify the failed assumption that prevents eventual absorption.
If every state is absorbing, what does the canonical matrix reduce to, and what are the sizes of the transient blocks?

Canonical Form of a Finite Absorbing Chain

What You'll Learn