Discrete markov chains with absorbing states : Exercises

Introduction

In these exercises we consider Markov chains that have a mixture of transient and absorbing states. In problems of this type the aim is almost always to calculate the probability of finishing in each of the absorbing states and to calculate the expected number of steps till absorbtion.

Example problems

Click on the problems to reveal the solution

Problem 1

A discrete random variable, $X$ , can take the values $X \in \{0,1,2\}$ according to a discrete Markov Process described by the transition matrix: $\mathbf{P} = \left( \begin{matrix} 0.6 & 0.1 & 0.3 \\ 0.2 & 0.2 & 0.6 \\ 0 & 0 & 1 \end{matrix} \right) \nonumber$ Find the hitting times for each of the transient states in this chain. That is find the expected number of steps required until absorption occurs.

The Markov chain given in the question has two transient states and one recurrent state. The recurrent state is state 2 and as such the matrix has already been arranged in the required form for this type of problem; namely:

$\begin{equation} P = \left( \begin{matrix} Q & R \\ 0 & I \end{matrix} \right) \nonumber \end{equation}$ with

$Q$ connecting the transient states to the transient states and

$R$ connecting the transient states to the recurrent states. In this question we thus have:

$\mathbf{Q} = \left( \begin{matrix} 0.6 & 0.1 \\ 0.2 & 0.2 \end{matrix} \right) \qquad \textrm{and} \qquad \mathbf{R} = \left( \begin{matrix} 0.3 0.6 \end{matrix} \right)$ To calculate the vector of hitting times,

$\mathbf{h}$ , for this chain we need to use:

$\mathbf{h} = ( \mathbf{I} - \mathbf{Q} )^{-1}\mathbf{1}$ and as such we need to invert a

$2\times2$ matrix as shown below:

$( I - Q )^{-1} = \left( \begin{matrix} 0.4 & -0.1 \\ -0.2 & 0.8 \end{matrix} \right)^{-1} = \frac{1}{ 0.4\times0.8 - 0.1 \times 0.2 } \left( \begin{matrix} 0.8 & 0.1 \\ 0.2 & 0.4 \end{matrix} \right) = \left( \begin{matrix} 8/3 & 1/3 \\ 2/3 & 4/3 \end{matrix} \right)$ When this matrix is multiplied by a vector containing all ones we get the desired vector of hitting times:

$\mathbf{h} = ( \mathbf{I} - \mathbf{Q} )^{-1} \mathbf{1} = \left( \begin{matrix} 8/3 & 1/3 \\ 2/3 & 4/3 \end{matrix} \right) \left( \begin{matrix} 1 \\ 1 \end{matrix} \right) = \left( \begin{matrix} 3 \\ 2 \end{matrix} \right)$ Now, obviously, calculating the hitting probabilities using:

$\mathbf{H} = ( \mathbf{I} - \mathbf{Q} )^{-1}\mathbf{R}$ is pointless because there is only one recurrent (absorbing) state. Lets do it anyway, however, in order to confirm that the formula above gives a result that is in accordance with our intuition.

$\mathbf{H} = ( \mathbf{I} - \mathbf{Q} )^{-1} \mathbf{R} = \left( \begin{matrix} 8/3 & 1/3 \\ 2/3 & 4/3 \end{matrix} \right) \left( \begin{matrix} 0.3 \\ 0.6 \end{matrix} \right) = \left( \begin{matrix} 4/5 + 1/5 \\ 1/5 + 4/5 \end{matrix} \right) = \left( \begin{matrix} 1 \\ 1 \end{matrix} \right)$

Problem 2

Consider a Markov chain with the following transition matrix. $\mathbf{P} = \left( \begin{matrix} 1/3 & 1/3 & 1/3 \\ 0 & 1/2 & 1/2 \\ 0 & 0 & 1 \end{matrix} \right)$ Which of the states in this graph is absorbing and what is the expected time till absorption if my initial state is selected at random.

In this chain states 1 and 2 are transient and state 3 is recurrent.

The time taken to absorption if the initial state is selected at random,

$\mathbf{E}(T)$ , is equal to:

$\mathbf{E}(T) = \frac{5}{2} \times \frac{1}{3} + 2 \times \frac{1}{3} + 0 \times \frac{1}{3} = \frac{3}{2}$

Problem 3

A Markov chain, between the states $X=0,1,2,3,4$ , is described by the following transition matrix: $\mathbf{P} = \left( \begin{matrix} 1 & 0 & 0 & 0 & 0 \\ 0.3 & 0.6 & 0 & 0 & 0.1 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0.2 & 0.3 & 0.3 & 0.2 \end{matrix} \right)$ Draw the transition graph for this chain, and show that $X=0,2$ are transient states. Once you have done this Partition the transition matrix so that $P = \left( \begin{matrix} Q & R \\ 0 & I \\ \end{matrix} \right) \qquad ,$ with $Q$ connecting the transient states so that you can calculate the hitting probability matrix: $h = (I-Q)^{-1}R \qquad ,$ and the hitting times. These hitting times should tell you the expected number of steps starting from the transient states, until absorption occurs.

The transition graph in this case looks like this:

The partitioned matrix looks like this:

$P = \left( \begin{matrix} 0.6 & 0.1 & 0.3 & 0 & 0 \\ 0.2 & 0.2 & 0 & 0.3 & 0.3 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 \end{matrix} \right)$ The hitting probability matrix in this case is:

$\mathbf{H} = \left( \begin{matrix} 0.8 & 0.1 & 0.1 \\ 0.2 & 0.4 & 0.4 \end{matrix} \right)$ The hitting times are:

$\mathbf{h} = \left( \begin{matrix} 3 \\ 2 \end{matrix} \right)$

Problem 4

A university introduces a new mathematics degree structure. The course is only two years long but students have to resit a year if they fail their final examinations. Students also have the option to resit the first and second years if they feel they did particularly poorly during year 2. In any given year students perform as follows in the two years:

Fraction passed Fraction failed Fraction dropped out

Year 1 0.1 0.6 0.3

Fraction passed Fraction repeat year 1 Fraction repeat year 2

Year 2 0.6 0.2 0.2

Construct a Markov chain based on this information and use this chain to calculate the probability that a student starting this course will complete it and the expected number of years a student will spend at university.

The Markov chain in this question contains four states. In the matrix given below the states are as follows

Student in year 1
Student in year 2
Student dropped out of year 1
Student graduated from year 2

Notice that states 1 and 2 are thus transient and that states 3 and 4 are recurrent:

$\mathbf{A} = \left( \begin{matrix} 0.6 & 0.1 & 0.3 & 0 \\ 0.2 & 0.2 & 0 & 0.6 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{matrix} \right)$ By using the same techniques that were used to solve the other problems on this page we can determine that the probability a student completes the course is equal to

$\frac{3}{15}$ and that on average each student spends three years at university.

Problem 5

The Markov chain with the one step transition matrix given below contains two recurrent classes. The first of these $R_1$ includes states 1 and 2 while $R_2$ includes states 5,6 and 7. Draw the transition graph for this chain and discuss the limiting behaviour of this chain. Then, assuming $X_0=3$ , find the probability that the chain gets adsorbed in $R_1$ . $\mathbf{A} = \left( \begin{matrix} 0.5 & 0.5 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0.5 & 0 & 0 & 0.5 & 0 & 0 & 0 \\ 0 & 0.25 & 0.25 & 0 & 0.5 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0.5 & 0 & 0.5 \end{matrix} \right)$

$\frac{5}{7}$

	Fraction passed	Fraction failed	Fraction dropped out
Year 1	0.1	0.6	0.3

	Fraction passed	Fraction repeat year 1	Fraction repeat year 2
Year 2	0.6	0.2	0.2