Example: the Cat and Mouse
Example: the cat and mouse
Suppose there are a timer and a row of five adjacent boxes, with a cat in the first box and a mouse in the fifth box at time zero. The cat and the mouse both jump to a random adjacent box when the timer advances. E.g. if the cat is in the second box and the mouse in the fourth one, the probability is one fourth that the cat will be in the first box and the mouse in the fifth after the timer advances. If the cat is in the first box and the mouse in the fifth one, the probability is one that the cat will be in box two and the mouse will be in box four after the timer advances. The cat eats the mouse if both end up in the same box, at which time the game ends.
The random variable K gives the number of time steps the mouse stays in the game. The Markov chain that represents this game contains the following five states specified by the combination of positions (cat,mouse). Note that while a naive enumeration of states would list 25 states, many are impossible either because the mouse can never have a lower index than the cat (as that would mean the mouse occupied the cat's box and survived to move past it), or because the sum of the two indices will always have even parity. In addition, the 3 possible states that lead to the mouse's death are combined into one: State 1: (1,3) State 2: (1,5) State 3: (2,4) State 4: (3,5) State 5: game over: (2,2), (3,3) & (4,4).We use a stochastic matrix, P displaystyle P (below), to represent the transition probabilities of this system (rows and columns in this matrix are indexed by the possible states listed above, with the pre-transition state as the row and post-transition state as the column).:1-8 For instance, starting from state 1 - 1st row - it is impossible for the system to stay in this state, so P 11 = 0 displaystyle P_11=0 ; the system also cannot transition to state 2 - because the cat would have stayed in the same box - so P 12 = 0 displaystyle P_12=0 , and by a similar argument for the mouse, P 14 = 0 displaystyle P_14=0 . Transitions to states 3 or 5 are allowed, and thus P 13 , P 15 0 displaystyle P_13,P_15
eq 0 . P = [ 0 0 1 / 2 0 1 / 2 0 0 1 0 0 1 / 4 1 / 4 0 1 / 4 1 / 4 0 0 1 / 2 0 1 / 2 0 0 0 0 1 ] . displaystyle P=beginbmatrix0&0&1/2&0&1/20&0&1&0&01/4&1/4&0&1/4&1/40&0&1/2&0&1/20&0&0&0&1endbmatrix. Long-term averagesNo matter what the initial state, the cat will eventually catch the mouse (with probability 1) and a stationary state = (0,0,0,0,1) is approached as a limit.:55-59 To compute the long-term average or expected value of a stochastic variable Y, for each state Sj and time tk there is a contribution of Yj,kP(S=Sj,t=tk). Survival can be treated as a binary variable with Y=1 for a surviving state and Y=0 for the terminated state. The states with Y=0 do not contribute to the long-term average. Phase-type representationAs State 5 is an absorbing state, the distribution of time to absorption is discrete phase-type distributed.
Suppose the system starts in state 2, represented by the vector [ 0 , 1 , 0 , 0 , 0 ] displaystyle ,1,0,0, . The states where the mouse has perished do not contribute to the survival average so state five can be ignored. The initial state and transition matrix can be reduced to, = [ 0 , 1 , 0 , 0 ] , T = [ 0 0 1 2 0 0 0 1 0 1 4 1 4 0 1 4 0 0 1 2 0 ] , displaystyle boldsymbol tau =,1,0,,qquad T=beginbmatrix0&0&frac 12&00&0&1&0frac 14&frac 14&0&frac 140&0&frac 12&0endbmatrix, and ( I T ) 1 1 = [ 2.75 4.5 3.5 2.75 ] , displaystyle (I-T)^-1boldsymbol 1=beginbmatrix2.754.53.52.75endbmatrix, where I displaystyle I is the identity matrix, and 1 displaystyle mathbf 1 represents a column matrix of all ones that acts as a sum over states. Since each state is occupied for one step of time the expected time of the mouse's survival is just the sum of the probability of occupation over all surviving states and steps in time, E [ K ] = ( I T T 2 ) 1 = ( I T ) 1 1 = 4.5. displaystyle E[K]=boldsymbol tau left(ITT^2cdots
ight)boldsymbol 1=boldsymbol tau (I-T)^-1boldsymbol 1=4.5. Higher order moments are given by E [ K ( K 1 ) ... ( K n 1 ) ] = n ! ( I T ) n T n 1 1 . displaystyle E[K(K-1)dots (K-n1)]=n!boldsymbol tau (I-T)^-nT^n-1mathbf 1 ,..
