Appendix: Absorbing Markov Chains

Motivating Example: Escaping a Maze¶

A student finds themselves in a strange maze of connected rooms. Some rooms are marked as exits. Once the student reaches one, they leave the maze and do not return. The other rooms are ordinary: the student moves between them until they reach an exit. Each turn, the student chooses a connected room uniformly at random.

Suppose the maze consists of six rooms labeled 1 through 6, with rooms 5 and 6 being exits. The student starts in one of the other rooms and moves randomly along available corridors. The structure of the maze is shown below:

• Room 1 connects to Rooms 2 and 3
• Room 2 connects to Rooms 1 and 4
• Room 3 connects to Rooms 1, 4, and 5
• Room 4 connects to Rooms 2, 3, and 6
• Rooms 5 and 6 are absorbing exits

Let $P$ be the transition matrix, where rows and columns correspond to the rooms in order:

Rooms 5 and 6 are absorbing: the student remains there once entered. The rest are transient. In the following sections, we will compute:

• The expected number of steps before exiting the maze
• The probability of exiting through Room 5 versus Room 6
• The expected number of visits to each room

This chapter will describe a powerful mathematical tool: Markov Chains and in particular Absorbing Markov Chains.

Theory¶

Definition of a Markov Chain¶

Let $S = \{s_1, s_2, \dots, s_n\}$ be a finite set of states. A Markov chain is defined by:

• A sequence of random variables $X_0, X_1, X_2, \dots$, where each $X_t \in S$
• A transition probability matrix $P \in \mathbb{R}\_{\geq 0}^{n \times n}$, where

with $\sum_{j=1}^nP_{ij}=1$ for all $1\leq i \leq n$.

A state of the Markov chain can be described by a probability distribution vector $\pi\in\mathbb{R}_[0, 1]^1$ such that $\sum_{i=1}^n \pi_i=1$.

This gives:

and so:

Example: Escaping the Maze¶

Let us assume that students are known to start in one of the room with equal probability. This implies that:

1. Calculate $\pi ^{(1)}$

2. Calculate $\pi ^{(2)}$

3. Given that:

   $$P ^ {1000} \approx \begin{pmatrix} 0.& 0.& 0.& 0.& 0.5455& 0.4545\\ 0.& 0.& 0.& 0.& 0.4545& 0.5455\\ 0.& 0.& 0.& 0.& 0.6364& 0.3636\\ 0.& 0.& 0.& 0.& 0.3636& 0.6364\\ 0.& 0.& 0.& 0.& 1.& 0. \\ 0.& 0.& 0.& 0.& 0.& 1. \end{pmatrix}$$

   (A1.6)

   What is the likely location of a student after 1000 time steps?

4. We have:

2. We have:

$$

$$

3. Finally:

We note that after 1000 time steps all of our probability is in the last two states. This is due to the nature of the maze but also the nature of the particular type of Markov chain which is an absorbing Markov chain: the last two states are absorbing states.

Definition: Absorbing Markov Chain¶

A Markov chain with transition matrix $P$ is absorbing if:

1. It has at least one absorbing state, i.e., a state $i$ such that $P_{ii} = 1$.

2. From every non-absorbing (transient) state $j$, there is a non-zero probability of reaching some absorbing state in a finite number of steps.

In other words, the chain cannot get “stuck” forever in a subset of transient states.

An absorbing Markov chain is a Markov chain whose transition matrix $P$ can be written (up to an ordering of states) in the following canonical form:

where:

• $Q$ is the transient submatrix: it contains the probabilities of transitions from transient state to transient state.
• $R$ is the transition to absorption submatrix: it contains the probabilities of transition from transient state to absorption state.

Example: The Maze as an absorbing Markov chain¶

For Motivating Example: Escaping a Maze the Markov chain $P$ can be written in the form of (A1.10) with:

Definition: Fundamental Matrix¶

For an absorbing Markov chain in the form (A1.10) the fundamental matrix $N$ is given by:

The entry $N_ij$ gives the expected number of times the process is in transient state $j$ before being absorbed having started in state $i$.

Example: Fundamental matrix of the Maze¶

For Motivating Example: Escaping a Maze the fundamental matrix is given by:

This inverse can be computed, a technique for doing this will be reviewed in Definition: Gauss-Jordan Method for inverting a matrix to give:

We can read from this matrix that for example, starting in state $i=2$ the student will visit state $j=3$ on average $N_{23}=1.36$ times.

This will allow us to identify which absorption state is the most likely.

Definition: Absorption Probability Matrix¶

For an absorbing Markov chain in the form (A1.10) the absorption probability matrix $B$ is given by:

The probability of being absorbed in to absorbing state $j$ having started at state $i$ is $B_{ij}$.

Example: Probability of absorbing state in the Maze¶

For Motivating Example: Escaping a Maze the absorption probability matrix is given by:

Definition: Gauss-Jordan Method for inverting a matrix¶

The Gauss-Jordan Method for inverting a non-singular matrix $A\in\mathbb{R}^{n \times n}$:

1. Set up the augmented matrix $[A \mid I]$, where $I$ is the $n \times n$ identity matrix.
2. Use row operations:
   • Swap rows;
   • Scaling rows;
   • Adding scalar multiples of a row to another row.
3. One the left hand side of the augmented matrix become $I$ the right hand side is $A^{-1}$.

Example: Compute the inverse of a 4 by 4 matrix¶

Let us compute the inverse of:

First we create the augmented matrix:

Let us add $1/2$ row 1 to row 2 and $1/3$ row 1 to row 3:

Let us multiple row 2 by $4/3$ (to create a leading 1):

Let us:

• Add $1/2$ of row 2 to row 1;
• Add $1/6$ of row 2 to row 3.
• Add $1/3$ of row 2 to row 4.

Let us multiply row 3 by $9/7$:

Let us:

• Add $2/3$ of row 3 to row 1;
• Add $1/3$ of row 3 to row 2.
• Add $4/9$ of row 3 to row 4.

Let us multiply row 4 by $21/11$:

Let us:

• Add $5/7$ of row 4 to row 1;
• Add $6/7$ of row 4 to row 2.
• Add $4/7$ of row 4 to row 3.

This has created the identity matrix on the left and results in the following inverse of $A$ (which was used in Example: Fundamental matrix of the Maze):

Exercises¶

Exercise: Transition Classification¶

Consider the following Markov chain with transition matrix:

1. Identify which states are transient and which are absorbing.
2. Write $P$ in canonical form.
3. Compute the fundamental matrix $N$.
4. Use $N$ to compute the expected number of steps until absorption starting from each transient state.

Exercise: Expected Visits¶

Let $P$ be the maze transition matrix from Section Motivating Example: Escaping a Maze. Suppose the student starts in Room 1.

1. How many times on average will the student visit Room 4 before reaching an exit?
2. Which ordinary room is visited most often in expectation when starting from Room 3?

Exercise: Symbolic Fundamental Matrix¶

Let

where $0 < a, b < 1$.

1. Compute the fundamental matrix $N = (I - Q)^{-1}$ symbolically.
2. Express the expected number of total steps before absorption from each starting state in terms of $a$ and $b$.

Exercise: Absorption Probabilities¶

Suppose a Markov chain has:

1. Compute the fundamental matrix $N$.
2. Compute the absorption probability matrix $B = NR$.
3. Interpret the meaning of $B_{12}$.

Programming¶

The main computational tools required in this chapter are matrix manipulations. In this section, we demonstrate two Python libraries that support this: one for numerical computation and one for symbolic computation. These operate in different number systems, allowing both approximate and exact linear algebra.

Using Numpy for Numeric Matrix Calculations¶

Numpy Harris et al., 2020 is the standard Python library for numerical computations. Here are some basic examples:

import numpy as np

A = np.array(
    [
        [4, 5],
        [7, 8],
    ]
)
B = np.array(
    [
        [1 / 4, 1 / 5],
        [8, 7],
    ]
)

A + 7 * B

Matrix multiplication is carried out using the @ operator:

A @ B

To raise a matrix to a power or compute its inverse, we use the numpy.linalg submodule:

import numpy.linalg

np.linalg.matrix_power(A, 3)

np.linalg.inv(A)

Using Sympy for Symbolic Matrix Computations¶

Sympy Meurer et al., 2017 is the standard Python library for symbolic mathematics. It allows for exact arithmetic using symbolic expressions:

import sympy as sym

a = sym.Symbol("a")
b = sym.Symbol("b")
c = sym.Symbol("c")
d = sym.Symbol("d")

A = sym.Matrix(
    [
        [a, b],
        [c, d],
    ]
)

Most operations follow the same syntax as in Numpy. For matrix exponentiation and inversion:

A ** 3

A.inv()

Using Sympy for Exact Row Operations¶

Row operations can also be performed using Sympy with exact rational arithmetic. The S operator creates exact symbolic constants:

A = sym.Matrix(
    [
        [1          , -sym.S(1)/2, -sym.S(1)/2, 0          , 1, 0, 0, 0],
        [-sym.S(1)/2, 1          , 0          , -sym.S(1)/2, 0, 1, 0, 0],
        [-sym.S(1)/3, 0          , 1          , -sym.S(1)/3, 0, 0, 1, 0],
        [0          , -sym.S(1)/3, -sym.S(1)/3, 1          , 0, 0, 0, 1],
    ]
)
A

To add $1/2$ of row 1 to row 2, and $1/3$ of row 1 to row 3:

A[1, :] = A[0, :] / 2 + A[1, :]
A[2, :] = A[0, :] / 3 + A[2, :]
A

To scale row 2 by $4/3$:

A[1, :] = 4 * A[1, :] / 3
A

Notable Research¶

The first formal description of the canonical form of an absorbing Markov chain is given in Snell, 1959, which served as a precursor to the influential book published in 1960 and later reissued in Kemeny & Snell, 1976.

Absorbing Markov chains have a wide range of applications. Of particular relevance to this book is their use in discrete models of evolutionary dynamics, as discussed in Moran Process. A notable example of this approach appears in Nowak & Sigmund, 2004.

Beyond the scope of this book, absorbing Markov chains have been applied to many other domains, demonstrating their versatility and theoretical interest:

• The original PageRank algorithm developed by Google has been analyzed through the lens of absorbing Markov chains Bianchini et al., 2005Langville & Meyer, 2004.
• In Palmer et al., 2018, absorbing chains are used to model deadlock in queuing systems, including applications in traffic flow and healthcare.
• The dynamics of battles in the board game Risk are captured using absorbing Markov chains in Tan, 1997Osborne, 2003.
• Student retention processes are modelled using absorbing chains in Tedeschi et al., 2023.

Conclusion¶

In this appendix, we explored absorbing Markov chains through both theory and application. These models provide powerful tools for analysing systems where eventual absorption is guaranteed — such as escape processes, games, and evolutionary dynamics.

The key concepts covered in this chapter are summarised Table A1.1.