Say you have a Markov chain $\{X_{n}\}$ with five states.

How can I calculate the probability that the chain will visit state $3$ before state $4$ given that we start in State $0, 1, 2, 3,$ and $4$?

I know If we start in state $3$ then it's $1$ and if we start in $4$ then it's 0.

I am having more difficulty with 0, 1, and 2. I have read through many markov chain chapter but am still not able solve the problem. Can someone please give me guidance in this exercise?

  • $\begingroup$ If you start at state $3,$ does that mean you got to $3$ before you get to $4$? Or is there always one step? $\endgroup$ – Thomas Andrews Oct 15 '19 at 20:34

Let $p_i$ be the probability that starting in state $i$ you get to state $3$ before state $4.$ Then you get $$\begin{align}p_0&=0.1p_0+0.2p_1+0.3\\p_1&=0.4p_0+0.3p_2+0.1\\p_2&=0.5p_0+0.1p_1+0.1p_2 + 0.2\\ p_3&=0.4p_1\\ p_4&=0.1p_0+0.6p_1+0.1p_2+0.1\end{align}$$

Rewrite this as a matrix equation, where you have a matrix $A$ and the equation:

$$A\begin{pmatrix}p_0 \\ p_1 \\ p_2\\ p_3 \\ p_4\end{pmatrix}=\begin{pmatrix}0.3 \\ 0.1\\0.2\\0\\0.1\end{pmatrix}$$

Then you get:

$$\begin{pmatrix}p_0 \\ p_1 \\ p_2\\ p_3 \\ p_4\end{pmatrix}=A^{-1}\begin{pmatrix}0.3 \\ 0.1\\0.2\\0\\0.1\end{pmatrix}$$

This assumes that starting at state $3$ does not count as reaching state $3$ and likewise starting by $4.$

If starting at states $3$ and $4$ counts as reaching those states, then $p_3=1.0$ and $p_4=0.0$ and you can solve the first three equations for $p_0,p_1,p_2.$

Indeed, you get the same values for $p_0,p_1,p_2$ with either reading, so you might as well just solve for $p_0,p_1,p_2$ first and then compute $p_4$ and $p_5$ from the linear equations. That requires only inverting a $3\times 3$ matrix, rather than a $5\times 5$ matrix.

More generally, if $M=\left(m_{ij}\right)_{1\leq i,j\leq n+2}$ is the matrix for a Markov process with $n+2$ states, $1,2,\dots,n+2$ Then $p_i,$ the probability that you reach state $n+1$ before reaching state $n+2$ is computed as follows.

  1. Let $B=\left(m_{ij}\right)_{1\leq i,j\leq n}$ be the top left $n\times n$ submatrix of $M.$

  2. Then, if $I-B$ is invertible, you get:

$$\begin{pmatrix}p_1\\p_2\\ \vdots\\ p_n \end{pmatrix}=(I-B)^{-1}\begin{pmatrix}m_{1,n+1}\\m_{2,n+1}\\ \vdots\\ m_{n,n+1}\end{pmatrix}$$

  1. If $I-B$ is not invertible, then you've got that some subset of the states never reach state $n+1$ or $n+2.$ $I-B$ being invertible coincides with the case when $B,B^2,B^3,\cdots$ converge to zero.

  2. $p_{n+1}$ and $p_{n+2}$ can be computed from $p_1,\dots,p_n$ pretty easily, in the case when you require at least one step. In that case, for $k=n+1,n+2$ you have: $$p_{k}=m_{k,n+1}+\sum_{i=1}^{n} m_{ki}p_i$$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy