1
$\begingroup$

Let's say I have the following scenario:

A mouse is put into a maze that's constructed as below:

enter image description here

There are 9 rooms with connections between the rooms as indicated with a "gap" in the "walls". Assume the mouse moves through the rooms at random and that self-transitions are allowed. That is, if there are $k$ ways to leave a room (or stay in the same room), it chooses each of these with equal probability.

Question:

What is the long-term expected fraction of time the mouse spends in each room?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

This is a standard application of Markov chain convergence theory. You can abstract the room configuration as a graph, with 6 vertices having degree 2 (leaves), two side vertices degree 4 and central vertex degree 5: because of self-loops as pointed out in comment belwo. Let $\mu_i$ be the long-term probability of the mouse spending in room $i$, and let $p_{ij}$ be the transition probability from room $i$ to room $j$. Then one must have $$ \sum_i \mu_i p_{ij} = \mu_j$$

It's easy to see that $\mu_i \propto d_i$ where $d_i$ is the degree of room $i$ is one (projective) solution; to show uniqueness look up the proof of Perron-Frobenius Theorem.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Since self-transitions are allowed, doesn't that mean there are 6 vertices with degree 2? I.e., state 1 has 1/2 probability of self transitioning and 1/2 probability of transitioning to state 4? Similarly for state 4, it has 1/4 probability of transitioning to itself, state 1, state 5, and state 7, respectively, right? $\endgroup$
    – TeTs
    Commented Apr 26, 2014 at 16:21
  • $\begingroup$ Yes. The rest follows the same. In fact if there are leaves, then the chain is not irreducible. $\endgroup$
    – John Jiang
    Commented Apr 30, 2014 at 21:41
  • $\begingroup$ Leaves are not related to reducibility. Here, if there are leaves, the chain is periodic. Note that periodicity would not change the fact that the proportion of time spent in each state converges, hence the addition of loops is (slightly artificial, if you ask me, and) not needed to solve the question. $\endgroup$
    – Did
    Commented Jul 5, 2014 at 9:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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