Editing Stochastic matrix (section)

== Example: Cat and mouse ==

Suppose there is a timer and a row of five adjacent boxes. At time zero, a cat is in the first box, and a mouse is in the fifth box. The cat and the mouse both jump to a random '''adjacent''' box when the timer advances. For example, if the cat is in the second box and the mouse is in the fourth, the probability that ''the cat will be in the first box '''and''' the mouse in the fifth after the timer advances'' is one fourth. If the cat is in the first box and the mouse is in the fifth, the probability that ''the cat will be in box two and the mouse will be in box four after the timer advances'' is one. The cat eats the mouse if both end up in the same box, at which time the game ends. Let the [[random variable]] ''K'' be the time 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 (mathematics)|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, <math>P</math> (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).  For instance, starting from state 1 – 1st row – it is impossible for the system to stay in this state, so <math>P_{11}=0</math>; the system also cannot transition to state 2 – because the cat would have stayed in the same box – so <math>P_{12}=0</math>, and by a similar argument for the mouse, <math>P_{14}=0</math>. Transitions to states 3 or 5 are allowed, and thus <math>P_{13},P_{15}\neq0</math> .

<math display="block"> P = 
\begin{bmatrix}
    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
\end{bmatrix}.</math>

===Long-term averages===

No matter what the initial state, the cat will eventually catch the mouse (with probability 1) and a stationary state '''&pi;''' = (0,0,0,0,1) is approached as a limit. To compute the long-term average or expected value of a stochastic variable <math>Y</math>, for each state <math>S_j</math> and time <math>t_k</math> there is a contribution of <math>Y_{j,k}\cdot P(S=S_j,t=t_k)</math>. Survival can be treated as a binary variable with <math>Y=1</math> for a surviving state and <math>Y=0</math> for the terminated state. The states with <math>Y=0</math> do not contribute to the long-term average.

===Phase-type representation===
[[Image:Mousesurvival.jpg|thumb|right|upright=1.6|The survival function of the mouse. The mouse will survive at least the first time step.]]

As State 5 is an absorbing state, the distribution of time to absorption is [[discrete phase-type distribution|discrete phase-type distributed]]. Suppose the system starts in state 2, represented by the vector <math>[0,1,0,0,0]</math>. The states where the mouse has perished don't contribute to the survival average so state five can be ignored. The initial state and transition matrix can be reduced to,

<math display="block">\boldsymbol{\tau}=[0,1,0,0], \qquad T=\begin{bmatrix}
    0          & 0           & \frac{1}{2}  &   0\\
    0          & 0           & 1            &   0\\
  \frac{1}{4}  & \frac{1}{4} &           0  & \frac{1}{4}\\
    0          & 0           & \frac{1}{2}  &   0
\end{bmatrix},</math> 

and 

<math display="block">(I-T)^{-1}\boldsymbol{1} =\begin{bmatrix}2.75 \\ 4.5 \\ 3.5 \\ 2.75\end{bmatrix},</math>

where <math>I</math> is the [[identity matrix]], and <math>\mathbf{1}</math> 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 [[Matrix polynomial#Matrix geometrical series|sum]] of the probability of occupation over all surviving states and steps in time,

<math display="block">E[K]=\boldsymbol{\tau} \left (I+T+T^2+\cdots \right )\boldsymbol{1}=\boldsymbol{\tau}(I-T)^{-1}\boldsymbol{1}=4.5.</math>

Higher order moments are given by

<math display="block">E[K(K-1)\dots(K-n+1)]=n!\boldsymbol{\tau}(I-{T})^{-n}{T}^{n-1}\mathbf{1}\,.</math>