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

enter image description here

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

  • $\begingroup$ Is the cat moving? Is the mouse moving? (Maybe even the cheese is moving?) What happens when the cat and mouse simultaneously move onto the cheese square? $\endgroup$ – whuber Dec 6 '20 at 2:30

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%.


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.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.