Compacting the Cat & Mouse State Diagram and Transition Matrix

  The symmetry in the Cat & Mouse state diagram allows us to combine states with similar transitions. If we fold the original state diagram along a horizontal line through the center we can combine some of the (cat, mouse) positions into states which represent sets of the positions. So (1,2) and (1,3) become state 1, (2,1) and (2,3) become state 2 and (3,1) and (3,2) become state 3. The "exit" state is relabeled state 4. The rules that apply to the determination of survival after a change in positions remain unchanged.

Using the new state diagram assuming random changes we can fill in the components of the 4x4 transition matrix, P. The initial state and survival vector each have four entries. The calculations give similar results to those previously found and the expected survival time is 2 states following in initial state.

Again looking at the transitions between states in the diagram above we see that we can compact the diagram a little more due to the symmetry for states 1 and 3. Folding the diagram along a vertical line through the center gives a diagram with just 3 states.

The new state diagram can be used to fill in the transition matrix and we get similar results for the calculations.

By compacting the state diagram and mixing the states we lose information about the relative positions of the cat and mouse but the calculations come out the same. As in the original Cat and Mouse problem we could simplify by summing over just the survival states and replace the infinite sum Σ_k P^k with (I-P)^-1. If the initial positions are equally likely the initial probability for a state is proportional to the number of positions included in the state. So for the first diagram above the probability of starting in state 1 is 2/6 or 1/3 but in the second diagram it is 4/6 or 2/3. In either diagram the probability of starting in state 2 would be 1/3.