Formula for the Powers of the Cat & Mouse Transition Matrix

  I was able to derive a formula for the powers of part of the transition matrix for the cat and mouse problem by dividing it up into the sum of two matrices that have simple products. The transition matrix for the cat and mouse problem involves 7 states including the "exit" state but the state diagram can be broken up into two separate parts because two sets of states are mutually exclusive except for the "exit" state. So if we just consider the states 1, 2, 3 and 7 we get a 4x4 transition matrix P. This matrix can be written as a linear combination of two matrices, U and V, with P=U+0.5V. On multiplication we find that U²=U and we can define two other matrices X=UV and W=V² that can be used to find a simple multiplication table for the products of these four matrices.

We can then write each P^k as a linear combination of just three of these matrices. The functions odd(k) and even(k) allow us to select either V or W for the third matrix depending on whether k is odd or even. X is nearly identical with U but with the 1 replaced by a 0. We see from the formula that, for large k, P^k → U+X a matrix with all zeros except for 1s in the bottom row. Since the sum the initial probability vector, p_i, is 1 we find that the game always ends up in the same state, (U+X)p_i = (0,0,0,1), no matter what state the game starts in.