Probability of doing a specific Path in a Markov Chain

Question

My problem is the following: I have this graph, representing a Markov Chain:

For example, if I am in state 1, the probability of going in state 2 or 4 is $\frac{1}{2}$. So I'm saying that the probability of going in one specific state is uniform. Now, let's say that in state 2 there is a mouse and in state 5 there is cheese. Let's also say that in state 4 there is a cat.

What is the probability that the mouse meet the cat first rather than the cheese?

I know that this problem involves using the Markov Property (the future is based only on the present and not on the past), but I don't know how to step forward.

Thank you

Answer 1

These problems can usually be solved by writing the set of equations related to the states and the transition probabilities that you have.

Let us call $p_i$ the probability of arriving to the cheese (which is in state 5) from state $i$. We know that by Markov Property, our future is only dependent on our current position, and we can therefore use this as our only variable.
Then we will have the following set:

$$p_1 = \frac{1}{2}p_4 + \frac{1}{2}p_2$$ $$p_2 = \frac{1}{2}p_1 + \frac{1}{2}p_3$$ $$p_3 = \frac{1}{3}p_4 + \frac{1}{3}p_2 + \frac{1}{3}p_6$$ $$p_4 = 0$$ $$p_5 = 1$$ $$p_6 = \frac{1}{3}p_3 + \frac{1}{3}p_5 + \frac{1}{3}p_7$$ $$p_7 = p_6$$ All of these are simply given by the transition probabilities, with the exception of $p_4$ and $p_5$. By definition, the probability of arriving to the cheese if we meet the cat (i.e. we are on 4) is 0, while it is 1 if we are already in state 5.
From here you can solve your linear equation.

EDIT: As previously mentioned, there was a good chance of me making an error in solving the equations. Thank you user2974951 for the pointer, I redid the equation and find $p_2 = \frac{2}{11}$ which is indeed around 18%
Given that the cheese and the cat are the only absorbing states of your Markov Chain, it means that the probability that it finds the cat first is $1-p_2$, which is around 81%.

Answer 2

Define the transition matrix $T$ as

$T=\begin{bmatrix} 0 & \frac12 & 0 & \frac12 &0&0&0 \\ \frac12 & 0 & \frac12 & 0&0&0&0 \\ 0 & \frac13 &0& \frac13 &0& \frac13 &0 \\ 0 & 0 &0&1&0&0&0 \\0&0&0&0&1&0 &0\\0&0&\frac13&0&\frac13&0&\frac13\\0&0&0&0&0&1&0 \end{bmatrix}$.

Calculate $P=T^n$ with $n$ being a sufficiently large integer, (e.g. $n>40$). Obviously, $P$ is a 7x7 matrix. The element $P(i,j)$ then gives the probability that the mouse starts from Point $i$ and reaches Point $j$. For instance, $P(2,4)=0.8182$ and $P(2,5)=0.1818$, indicating that the probability that the mouse reaches Point 4 (or Point 5) is 0.8182 (or 0.1818) starting from Point 2.

Answer 3

Cut the connection from $4$ to $5$. Introduce an extra state, say $4^\prime$. It can be reached only from $4$ with probability $p_{45}$, i.e., transition probability from $4$ to $5$ and it arrives at $5$ with probability 1.

Calculate the $P(2,5)-P(2, 4^\prime)$. This is the probability that the mouse ends at $5$ without being eaten.

I hope this helps.