The probability that the mouse ever gets to eat the cheese

markov chainsprobabilitystochastic-processes

I'm doing an exercise about Markov chain.

A merry mouse moves in a maze. If it is at time $n$ in a room with $k$ horizontal or vertical adjacent rooms, it will be at time $n+1$ in one of the $k$ adjacent rooms, choosing one at random, each with probability $1 / k$. A fat lazy cat remains all the time in room $3,$ and a piece of cheese waits for the mouse in room $5$ The mouse starts in room $1$. See the following figure:

enter image description here

The cat is not completely lazy: If the mouse enters the room inhabited by the cat, the cat will eat it. Also, if the mouse eats the cheese, it rests forever. Let $X_{n}$ be the position of the mouse at time $n$.

What is the probability that the mouse ever gets to eat the cheese?

From the graph, the transition matrix is as follows:

$$P=\begin{pmatrix}0 & 1/2 & 0 & 1/2 & 0 \\
1/2 & 0 & 1/2 & 0 & 0 \\
0 & 1/2 & 0 & 1/2 & 0 \\
1/3 & 0 & 1/3 & 0 & 1/3 \\
0 & 0 & 0 & 1 & 0 \\
\end{pmatrix}$$

Then the probability that the mouse ever gets to eat the cheese is $$\mathbb P \left (\forall n \in \mathbb N:X_n \neq 5 \right )$$

Could you please leave me some hints to compute this probability? Thank you so much!

Best Answer

The transition matrix should actually be $$ P = \begin{pmatrix} 0 & 1/2 & 0 & 1/2 & 0\\ 1/2 & 0 & 1/2 & 0 & 0\\ 0 & 0 & 1 & 0 & 0\\ 1/3 & 0 & 1/3 & 0 &1/3\\ 0 & 0 & 0 & 0 & 1 \end{pmatrix}. $$ Let $X_n$ be the state the mouse is in at time $n$, then $\{X_n:n=0,1,2,\ldots\}$ is a Markov chain on $\{1,2,3,4,5\}$ with the above transition probabilities. We want to compute $\mathbb P(\tau_1)$, where $$ \tau_i = \inf\{n>0: X_n = 5 \mid X_0 = i\},\quad i\in\{1,2,3,4,5\}. $$ It is clear that $\mathbb P(\tau_3)=0$ and $\mathbb P(\tau_5)=1$. To compute the remaining $\tau_i$ we have the system of linear equations \begin{align} \mathbb P(\tau_1) &= P_{12}\mathbb P(\tau_2) + P_{14}\mathbb P(\tau_4)\\ \mathbb P(\tau_2) &= P_{21}\mathbb P(\tau_1)\\ \mathbb P(\tau_4) &= P_{41}\mathbb P(\tau_1) + P_{45}. \end{align} Substituting in the transition probabilities, we have \begin{align} \mathbb P(\tau_1) &= 1/2\mathbb P(\tau_2) + 1/2\mathbb P(\tau_4)\\ \mathbb P(\tau_2) &= 1/2\mathbb P(\tau_1)\\ \mathbb P(\tau_4) &= 1/3\mathbb P(\tau_1) + 1/3. \end{align} This yields $$ \mathbb P(\tau_1) = \frac27,\quad \mathbb P(\tau_2) = \frac17,\quad \mathbb P(\tau_4) = \frac37. $$ Indeed, if we compute $\lim_{n\to\infty}P^n$ (which exists since $P$ is aperiodic), we get $$ \left( \begin{array}{ccccc} 0 & 0 & \frac{5}{7} & 0 & \frac{2}{7} \\ 0 & 0 & \frac{6}{7} & 0 & \frac{1}{7} \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & \frac{4}{7} & 0 & \frac{3}{7} \\ 0 & 0 & 0 & 0 & 1 \\ \end{array} \right), $$ and the desired $\mathbb P(\tau_i)$ values can be read off the last column of this matrix.