# Finding probability of visiting one state given another

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?

• If you start at state $3,$ does that mean you got to $3$ before you get to $4$? Or is there always one step? – 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$$