I recently started to learn about Markov Chains and had a problem regarding the expected time to absorption:
Problem:
Markov has an untrained mouse that he place in a maze. The mouse may move between adjoining rooms, or stay in the same room at any time-step. At the exit of the maze is an enormous piece of unscented cheese where the mouse may leave from and never return. Given the following transition matrix:
$$\begin{pmatrix}\frac 1{10}&\frac 3{10}&\frac 35&0&0&0\\\frac 12&\frac 12 &0&0&0&0\\\frac 3{10}&0&\frac 1{10}&\frac 35&0&0\\0&0&\frac 3{10}&\frac 1{10}&\frac 3{10}&\frac 3{10}\\0&0&0&\frac 12&\frac 12&0\\0&0&0&0&0&1\\ \end{pmatrix}$$
(a) What is the probability it leaves the maze, given it started in State $i \quad \forall \ i \in[0,5]$ ??
(b) How long before it leaves the maze, given it started in State $i \quad \forall \ i \in[0,5]$ ?
My Attempt:
Well first I made a diagram to get the understanding of the problem visually. I replace the number States to letters, i.e. State $1$ as State $A$ etc. and wrote down the transition probabilities from the matrix.
(a) I think because there exists an absorbing state at the exit, then the probability of exiting must be $1$ a.s..
(b) I used First-Step-Analysis to find the expected time for each $i$.
Let $v_i$ be the expected time to exit from starting position $i$, i.e. $v_i =\Bbb E_i[T_{\{5\}}]$. Then solving the system of equations:
$$
\left\{
\begin{array}{ll}
v_A &=1+\frac 1{10} v_A+\frac 3{10} v_B+\frac 35 v_C \\
v_B &=1+\frac 12 v_A +\frac 12 v_B\\
v_C &=1+\frac 3{10} v_A+\frac 1{10} v_C+\frac 35 v_D \\
v_D &=1+\frac 3{10} v_C+\frac 1{10} v_D+\frac 3{10} v_E+\frac 3{10} v_F \\
v_E &=1+\frac 12 v_D+\frac 12 v_E\\
v_F &=0
\end{array}
\right.
$$
So I get the following solution:
$$\Bbb E_A[T_{\{5\}}]=14; \quad \Bbb E_B[T_{\{5\}}]=16 \quad \Bbb E_C[T_{\{5\}}]=11 \frac 13 \quad \Bbb E_D[T_{\{5\}}]=8 \frac 13 \quad \Bbb E_E[T_{\{5\}}]= 10 \frac 13$$
I'm not $100\%$ sure about the part (b).
My Question(s):
I was wondering, is there another way to look at this problem without using Markov Chains or First-Step-Analysis? I feel like there are geometric random variables involved here.
Also what would happen if there were 2 exits, could I apply the exact same principles or is something changing?
Thank you in advance!
Best Answer
Here's another approach:
A random walk on a connected, undirected, unweighted graph spends the same time on each edge in each direction. Thus the proportion of time it spends at a vertex is the number of edges incident at the vertex divided by twice the total number of edges. This still holds true if you weight the edges and even if the walk is periodic. You can check all this by checking that the corresponding distributions are invariant under transitions (where the transition probabilities are proportional to the edge weights).
In your case, we need self-loops in the graph, which complicates things, but only slightly. A self-loop only has one “direction”, so it only counts once in the sum of the edge weights, whereas normal edges count twice.
The expected return time of a vertex (the time it takes for the random walk starting at the vertex to return to the vertex, possibly immediately through a self-loop) is the reciprocal of the proportion of time the walk spends at the vertex.
What does all this have to do with your problem? Add a vertex for the exit and assign edge weights to the doors so that they yield your transition matrix. If you assign weight $3$ to the self-loop at $B$ to make all the edge weights come out as integers, you can work your way from $B$ through the maze to arrive at these edge weights:
The numbers in the doorways are the weights of the proper edges, the numbers next to the room labels are the weights of the self-loops. The sum (with self-loops counted once and proper edges counted twice) is $112$.
The return time for a random walk on this graph starting at the exit is $1$ plus the exit time $v_D$ from $D$. Thus
$$ v_D=\frac{112}{12}-1=8\frac13\;, $$
in agreement with your solution.
Now consider the subgraph comprising vertices $A$ through $D$, but without the self-loop at $D$. The sum of edge weights with multiplicities is $48$. The return time for a random walk on this subgraph starting from $D$ is $1$ plus the expected time to get from $C$ to $D$. Thus
$$ v_C=v_D+\frac{48}{12}-1=11\frac13\;, $$
again in agreement with your solution. I think you can figure out the rest yourself.
Note that this requires us to solve only simple linear equations, no systems of equations (including the part of figuring out the edge weights). This works whenever the mouse is in a tree.