Use of absorbing states in Markov chain

Elan Ding
Modified: June 18, 2018

Consider the following interesting problem written by Dr. Peter Kiessler:

Harry has a keen appreciation for precise and elegant use of the English language and cannot abide linguistic crudity. Above all else, he abhors the use of the dreaded f-word. One day a Mutant Creepazoid wanders in for a cup of coffee. The creepazoid’s brain has been all but destroyed by too much television and other toxic substances and has resulted in limited expressive abilities. In fact the conversation of the creepazoid consists primarily of the following phrases:

  • Ya know.
  • It was weird.
  • Like, I dunno, man.
  • Bummer.
  • It was awesome.
  • F-word.

The appearance of these phrases in the mutant creepazoid’s speech follows a Markov chain with the following transition matrix:

$$ P=\begin{bmatrix} .6 & .1 & .1 & .1 & .1 & 0 \\ .3 & 0 & .3 & .2 & .1 & .1 \\ .3 & .5 & 0 & .1 & .1 & 0 \\ .1 & .2 & .2 & 0 & .1 & .4 \\ .2 & .2 & 0 & .1 & 0 & .5 \\ .2 & .2 & .2 & .2 & .2 & 0 \end{bmatrix}. $$

  1. What is the expected number of transitions until the dreaded f-word is spoken?
  2. Harry bets Zeke \$10 that the phrase "It was weird" would appear before the phrase "It was awesome". What is Harry's expected earnings from this bet?

The problem can be solve using a powerful technique of defining absorving states. To help you better understand the rest of the post, I will refresh you memory on the most important results:

Definition. A discrete-time Markov chain is a sequence of random variables $X_1, X_2, X_3,...$ with the Markov property. That is,

$$ P(X_{n+1} = x \,|\, X_n = x_n, \cdots, X_0 = x_0) = P(X_{n+1} = x \,|\, X_n = x_n) $$ The countable possible values of $X_i$ form a set called the state space of of the Markov chain. The one-step-transition-matrix, $P$ of a Markov chain is the matrix whose $(i,j)$-th entry is

$$P_{i,j} = P(X_1 = \text{ State } j \,|\, X_0 = \text{ State } i)$$

The Chapman-Kolmogorov Equation. Let $P_{i,j}^{(n)}$ denote the probability $P(X_{n+k} = j\,|\, X_k = i)$ often abbreviated as $P_i(X_n=j)$. Then

$$ P_{i,j}^{(n+m)} = \sum_{k=0}^{\infty} P_{i,k}^{(n)}P_{k,j}^{(m)}, \quad n,m\geq 0 $$

Definition. Let $f_i$ denote the probability that starting at state $i$, the Markov chain will ever reenter $i$. State $i$ is recurrent if $f_i=1$, and transient if $f_i<1$.

Defining absorving state

Let $X_n$ be a Markov chain with state space $E$, and transition matrix $P = [P_{ij}]$. Let $J\subset E$ be a subset of the state space, and $a$ be an additional new state (not in $E$). Let $\tau_J^{(1)}$ denote the time until the Markov chain's first visit to a state in $J$. We define a new Markov chain $W_n$ by

$$ W_n = \begin{cases} X_n & \text{ if } n<\tau_J^{(1)} \\ a & \text{ if } n\geq \tau_J^{(1)} \end{cases} $$

$W_n$ is a Markov chain with state space $(E-J)\cup\{a\}$, and its transition matrix $Q$ is defined as

$$ \begin{aligned} Q_{a,a} &= 1 \\ Q_{i,a} &= \sum_{j\in J} P_{i,j} \text{ if } i\not\in J \\ Q_{i,j} &= P_{i,j} \text{ if } i,j \not\in J \end{aligned} $$

That is,

$$ Q = \begin{bmatrix} & \cdot & & Q_{1,a} \\ \cdot & P_{J^c} & \cdot & Q_{2,a} \\ & \cdot & & \cdot \\ 0 & 0 & \cdot & 1 \end{bmatrix} $$

The additional state $a$ introduced here is called an absorbing state. It is called thus because once the Markov chain enters this state, it will stay there, in a black hole, forever.

Given that the Markov chain starts in a state $i\in J^c$, the probability that the Markov chain will visit another state $j\in J^c$ in $m$ steps without visiting any states in $J$ is given by $Q_{i,j}^{(m)}$.

With this clever setup, we can quickly find the probability that the Markov chain will enter a state in $J$ in no more than $m$ steps given that it starts in a state $i \in J^c$ as:

$$ P_i(\tau_J^{(1)} \leq m) = P_i(W_m = a) = Q_{i,a}^{(m)}, \quad i \in J^c. $$

Given that the Markov chain starts in a state $i \in J^c$, the probability that the Markov chain will first visit a state $j\in J$ in exactly $m$ steps is given by

$$ P_i(\tau_j^{(1)} = m) = \sum_{r\not\in J} Q_{i,r}^{(m-1)} P_{r,j}, \quad i\in J^c,\,\, j\in J. $$

Moving in and between classes

The transition matrix can be divided into blocks:

$$ P=\begin{bmatrix} P_r & 0 \\ L & Q \end{bmatrix} $$

where $P_R$ is the transition matrix between recurrent states, $L$ is the transition matrix between transient states to recurrent states, and $Q$ is the transition matrix between transient states. Since it is impossible to go from a recurrent state to a transient state, the upper right corner block or $P$ is the 0 matrix.

Moving in transient states

Let $T$ denote the transient states, and $R$ the recurrent states. For $i,j \in T$, define $S=[s_{i,j}]$ to be a matrix where $s_{i,j}$ denote the expected number of time periods that the Markov chain visits state $j$, given that it starts in state $i$. Conditioning on the first transition yields the equation

$$ s_{i,j} = \delta_{i,j} + \sum_k Q_{i,k} s_{k,j} $$

where $\delta_{i,j}$ is the Kronecker delta function. In matrix notation we have

$$ S = I + QS \implies S=(I-Q)^{-1} $$

The matrix $S = (I-Q)^{-1}$ is called the fundamental matrix of a Markov chain.

Moving from transient states to recurrent states

For $i \in T$ and $j\in R$, define $U=[u_{i,j}]$ where $u_{i,j}$ denotes the probability that the Markov chain's first visit to a recurrent state is to state $j$. Then

$$ u_{i,j} = \sum_{n=0}^{\infty} \sum_{k\in T} Q_{i,k}^{(n)}L_{k,j}. $$

In matrix notation we have

$$ U = \sum_{n=0}^{\infty} Q^n L \implies U=L+QU. $$

If $|T|<\infty$, we can solve for $U$:

$$ U = (I-Q)^{-1}L = SL. $$

Now we are ready to answer the problem posed in the beginning.

Question 1. What is the expected number of transitions until the dreaded f-word is spoken?

Solution. Define a new Markov chain $W$ where states $T=\{1,2,3,4,5\}$ are transient states, and $W_{i,j} = P_{i,j}$ for $i,j\in T$. Define state 6 to be absorbing, so $W_{6, 6}=1$. Hence we can let $Q$ be the sub-matrix whose entries are the first 5 by 5 block of $P$. THat is,

$$ W = \begin{bmatrix} Q & \cdot \\ 0 & 1 \end{bmatrix} \quad \text{ where } \,\, Q = \begin{bmatrix} .6 & .1 & .1 & .1 & .1 \\ .3 & 0 & .3 & .2 & .1 \\ .3 & .5 & 0 & .1 & .1 \\ .1 & .2 & .2 & 0 & .1 \\ .2 & .2 & 0 & .1 & 0 \end{bmatrix}. $$

The fundamental matrix $S=(I-Q)^{-1}$ to be easily calculated:

$$ S = \begin{bmatrix} 5.18799163 & 1.48444829 & 1.16836256 & 1.02114455 & 0.8861947 \\ 3.22869308 & 2.27033268 & 1.19867215 & 0.97351519 & 0.76712131 \\ 3.56642852 & 1.77022444 & 2.08847514 & 1.00382478 & 0.84289529 \\ 2.06682543 & 1.0420726 & 0.82990546 & 1.5530057 & 0.54918092 \\ 1.89001948 & 0.85516346 & 0.55639749 & 0.55423252 & 1.38558129 \end{bmatrix} $$

where $S_{i,j}$ denotes the expected number of steps that the Markov chain is in the transient state $j$ given that it starts in another transient state $i$. Starting from state 3, the expected number of transitions until the Markov chain reach the absorbing state can be found by summing the third row of the fundamental matrix $S$. That is,

$$ \begin{aligned} E(3) &= 3.56642852 + 1.77022444 + 2.08847514 + 1.00382478 + 0.84289529 \\ & = 9.27184817 \text{ steps} \end{aligned} $$

where $E(i)$ denote the expected number of steps to reach state 6 starting from state $i$. Clearly $E(6) = 0$.

Just to offer you a different perspective, another way to solve the problem is by conditioning on the first transition, and solve the following system of equations:

$$ \begin{aligned} E(1) & = 0.6(E(1)+1) + 0.1(E(2)+1) + 0.1(E(3)+1) + 0.1(E(4) +1) + 0.1(E(5) +1) \\ E(2) & = 0.3(E(1)+1) + 0.3(E(3)+1) + 0.2(E(4) +1) + 0.1(E(5) +1) + 0.1 \\ E(3) & = 0.3(E(1)+1) + 0.5(E(2)+1) + 0.1(E(4)+1) + 0.1(E(5) +1) \\ E(4) & = 0.1(E(1)+1) + 0.2(E(2)+1) + 0.2(E(3)+1) + 0.1(E(5) +1) + 0.4 \\ E(5) & = 0.2(E(1)+1) + 0.2(E(2)+1) + 0.1(E(4)+1) + 0.5 \end{aligned} $$

Again the system of linear equations can be easily solve to have the solution:

$$ (9.74814173, 8.43833442, 9.27184816, 6.04099011, 5.24139424) $$

Note that the third number $E(3) = 9.27184816$ is the solution.

Question 2. Harry bets Zeke \$10 that the phrase "It was weird" would appear before the phrase "It was awexome". What is Harry's expected earnings from this bet?

Solution. Here we want to define both state 2 and state 5 as absorving, and let $Q$ be the transition matrix within transient states $\{1,3,4,6\}$:

$$Q = \begin{bmatrix} .6 & .1 & .1 & 0 \\ .3 & 0 & .1 & 0 \\ .1 & .2 & 0 & .4 \\ .2 & .2 & .2 & 0 \end{bmatrix} $$

Define $L$ to be the transition matrix from states $\{1,3,4,6\}$ to state $\{2,5\}$:

$$ L = \begin{bmatrix} .1 & .1 \\ .5 & .1 \\ .2 & .1 \\ .2 & .2 \end{bmatrix} $$

Using our previous result, we first find the matrix $U$:

$$ U = (I-Q)^{-1} L = \begin{bmatrix} 0.59800664 & 0.40199336 \\ 0.74418605 & 0.25581395 \\ 0.64784053 & 0.35215947 \\ 0.59800664 & 0.40199336 \end{bmatrix} $$

The probability we are interested is $U_{2,1} = 0.74418605$, which represents the probability that the Markov chain's first visit to an absorbing state is to state 2.

Hence the expected earning of the best is $$10\times 0.74418605 - 10\times(1-0.74418605)\approx 4.88.$$