9
$\begingroup$

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.

Maze

(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!

$\endgroup$
3
$\begingroup$

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:

enter image description here

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.

$\endgroup$
  • $\begingroup$ If the mouse is in a tree, you can also solve the system of linear equations by only using simple linear equations. $\endgroup$ – Phira Jun 24 '18 at 9:29
  • 1
    $\begingroup$ Wow this is actually a relatively nice solution and I can see it being applicable to a a range of similar problems. Thank you :) Just a brief question, when one finds the $v_C$ case, why do we ignore the self loop at $D$? Because it will be counted within $v_D$? $\endgroup$ – Tony Hellmuth Jun 24 '18 at 9:32
  • 1
    $\begingroup$ @TonyHellmuth: We want to force the walk on the subgraph to go from $D$ to $C$ in the first step. That's what allows us to say that the return time starting at $D$ is $1$ plus the time to get from $C$ to $D$. If we include the self-loop, that's no longer true; the first step of the walk starting at $D$ might already return to $D$ through the self-loop. $\endgroup$ – joriki Jun 24 '18 at 9:36
  • $\begingroup$ @Phira: Well, you still have to express variables in terms of other variables, substitute into equations, simplify and so on -- it's a non-local process, though you're certainly right that it's much more straightforward to do by hand than to solve a general system of linear equations. But this approach is a bit simpler yet; every step immediately yields a result without a chain of substitutions into other equations. $\endgroup$ – joriki Jun 24 '18 at 9:41
  • $\begingroup$ Aahhhh we are in some way double counting. Thanks @joriki $\endgroup$ – Tony Hellmuth Jun 24 '18 at 9:42
-1
$\begingroup$

Your solution us fine, it would work the same for two exits and other approaches would lead to an equivalent calculation because you will get the solutions of this linear system in the end even if you do not write it down.

$\endgroup$
  • $\begingroup$ Could you briefly touch on those other approaches? I would really appreciate it. Thank you for your answer :) $\endgroup$ – Tony Hellmuth Jun 24 '18 at 0:56

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.