I am really new to Stochastic processes, and this is one of the supplementary practice questions that I stumbled across whilst studying:
Modify the situation as described in
http://www.ucl.ac.uk/statistics/research/ltcc/stochastic/markovChainExample.pdf:
Now assume that the rat is in a maze of three cells (indexed by
$1-3$), and the outside (freedom) is still denoted by $0$. We still
assume that the rat does not learn from past mistake. Now given that
the transition matrix:
$$T=\begin{align} \begin{bmatrix} 1 & 0 & 0 & 0 \\1/2 & 0 & 1/2 & 0 \\1/3 & 1/3 & 0 & 1/3 \\ 2/3 & 0 & 1/3 & 0 \end{bmatrix} \end{align}$$
Required:(a) Find the probability that if the rat enters the maze at cell $1$,
it will exit the maze from cell $3$.(b) Suppose that the rat is outside, about to enter into the maze. Find the probability that it will eventually leave the maze from cell $3$.
I was told that the answer for part a (if I am not mistaken) is $2/13$. But I have no idea where to get it from, the closest that I can get is $1/5$. My approach is as follows:
So, what I first thought is that I can make state $3$ absorbing, along with state $0$:
$$T=\begin{align} \begin{bmatrix} 1 & 0 & 0 & 0 \\1/2 & 0 & 1/2 & 0 \\1/3 & 1/3 & 0 & 1/3 \\ 0 & 0 & 0 & 1 \end{bmatrix} \end{align}$$
Then I try to identify the fundamental matrix and multiply it with R (the lower left part of the matrix) and obtain:
$$FR=\begin{align} \begin{bmatrix} 4/5 & 1/5 \\ 3/5 & 2/5 \end{bmatrix} \end{align}$$
We can see that it ended up having a probability of $1/5$. I can understand if this is wrong, cause from cell $3$ there are $2/3$ chance that it will exit the maze, and another $1/3$ chance that it will go back to cell $2$. Can anybody let me know how can I proceed with this question correctly?
For part (b) I was told that the answer is $1/2$. I don't know if my intuition is right, I reasoned: since from the transition matrix we can figured that there are 1 way you can exit from cell $1$, 1 way you can exit from cell $2$, and 2 ways you can exit from cell $3$, we can see that the probability that it exits from cell $3$ is $2/4 = 1/2$. How can I mathematically show this?
Any help would be highly appreciated!
Best Answer
(a) I think your method fails because you can't make state $3$ absorbing. It has a path to state $2$ that stops you doing that.
If you want to use this kind of method with the fundamental matrix, you could split state $0$ into say, $0$ and $4$, with state $3$ going to $4$ instead of $0$. Then the required probability should be the $(1,4)^{th}$ entry of matrix $FR$ based on the new transition probability matrix.
However, a common way to solve this kind of problem uses first-step analysis (i.e. conditioning):
Let $p_i = P(\text{Exit from state $3$ starting from state $i$}),\; i=1,2,3$. So we want $p_1$. Conditioning on the next step:
\begin{align} p_1 &= \dfrac{1}{2} p_2 \\ p_2 &= \dfrac{1}{3} p_1 + \dfrac{1}{3} p_3 \\ p_3 &= \dfrac{2}{3} + \dfrac{1}{3} p_2 \\ \end{align}
Solve this system of equations to give:
$$p_1 = \dfrac{2}{13}.$$
$$\\$$
(b) I think there is some validity behind that method but it would need some justification probably based on the reversibility property of random walks on a graph. An argument based only on the number of exits isn't sufficient, IMO.
An easier method is just to continue the above solution for (a). That system of equations also gives
$$p_2 = \dfrac{4}{13}, \qquad p_3 = \dfrac{10}{13}.$$
Now, there are $2$ paths into state $3$ and $1$ path each into states $1$ and $2$. So the probability of entry via these states are:
\begin{align} P(\text{Entry via } 1) &= \dfrac{1}{4} \\ P(\text{Entry via } 2) &= \dfrac{1}{4} \\ P(\text{Entry via } 3) &= \dfrac{1}{2}. \end{align}
So,
\begin{align} P(\text{Exit via state $3$}) &= P(\text{Entry via } 1)p_1 + P(\text{Entry via } 2)p_2 + P(\text{Entry via } 3)p_3 \\ &= \dfrac{1}{4}\cdot \dfrac{2}{13} + \dfrac{1}{4}\cdot \dfrac{4}{13} + \dfrac{1}{2}\cdot \dfrac{10}{13} \\ &= \dfrac{1}{2}. \end{align}