# How is the prob matrix generated in Markov Chain - cat and mouse problem

#1

Hello,

While learning about Markov Chain I came across the below problem:

A simple Markov chain – cat and mouse
Suppose there is a row of five adjacent boxes, with a cat in the first box and a mouse
in the fifth box. At each ‘tick’ the cat and the mouse both jump to a random box next
to them. On the first tick the cat must jump to box 2 and the mouse to box 4 but on
the next ticks they may jump to the box they started in or to box 3.
When the cat and mouse are in the same box the cat catches the mouse and the
Markov chain terminates. Because there is an odd number of boxes between the
cat and mouse it’s easy to see that they will not jump past each other.
So Markov chain that corresponds to this contains the only five possible
combinations of (Cat,Mouse).

``````State 1: (1,3) State 2: (1,5) State 3: (2,4) State 4: (3,5) State 5:
(2,2), (3,3) & (4,4) # => cat catches the mouse
The matrix P = [0 0 .5 0 .5; 0 0 1 0 0; .25 .25 0, .25 .25; 0 0 .5
0 .5; 0 0 0 0 1] represents the probabilities of the transition from one state to
the next and the question is how long has the mouse got before it's caught. Its best
chance is starting in State 2 = (1,5).
``````

The matrix P is a stochastic matrix where all the probabilities along any row add up
to 1.