Cat & Mouse

  I found a cat and mouse problem in an article on Wikipedia that was used to illustrate the concept of a stochastic matrix and thought I would do a similar problem of my own and show how it can be solved using the transition matrix and initial state.

  In a 3 room apartment a cat is stalking a mouse. Neither is aware of the other's location and move to neighboring rooms at random. The mouse has an advantage in that it can go through a mouse hole connecting rooms 1 and 3 while the cat cannot. The cat captures the mouse if they end up in the same room or go through the same door. What is the expected survival time of the mouse if they start out in different rooms? Here's a floor plan.

  As in the article one can specify the survival states by the pair of positions (cat, mouse) with the values being 1, 2 and 3. There are 9 possible combinations 6 of which are survival states. The state diagram shows the allowed movements and events for ending the game.

The cat and mouse move randomly so each path leaving a state has equal probability. In the transition matrix P the columns correspond to an existing state and the rows to the next state. In the diagram and the first column we see that state 1 can change to states 2 and 7 with equal probability of 1/2. The second column shows that the second state has four paths leaving it and they are each are assigned a probability of 1/4. One can use the state diagram to fill in the rest of transition matrix. There is no way of leaving the final state so it just goes back to itself.

We can use 1 to indicate survival and 0 to indicate that the mouse has perished. The first calculation shows that the if the mouse is in any surviving state is can expect to survive two states on average. The zero at the end is for the terminal state. The last state included in the sum is 100 and approximates survival over an infinite number of steps. Powers of P are used to find the relative probabilities of a state after k steps. We see that the probability of survival after k steps is 1/2^k. This is an infinite geometric series and it's sum with r=1/2 is 1/(1-r)=2. The checks with the formula used for the expected value of survival. An infinite sum has to be approximated since we can't use the inverse of I-P to evaluate the sum of the matrix series. I-P doesn't have an inverse because the sum of all the columns is one making one line in P a linear combination of all the others.