Question

2. A mouse is let loose in the maze of Figure 1. From each compartment the mouse chooses one of the adjacent compartments with equal probability, independent of the past. The mouse spends 1 me unit in each compartment. Let {Xn, n 20 be the Markov chain that describes the position of the mouse for times n2 0. 4 Figure 1: A maze. (a) Determine the one-step transition matrix. (b) Use matrix multiplication on a computer to evaluate the probability that the mouse will be in compartment 6 at time n7, starting from compartment 4 at time n 0 (c) What is the probability that the mouse will be found in compartment 6 at some time n far away in the future?

Answer 1

(a)

The problem can be modeled as Markov chain with 6 states - 1, 2, 3, 4, 5 and 6 denoting the compartment number at any time.

From compartment 1, there is a way to compartment 2 and 3. Thus, the transition probability from state 1 to state 2 or state 3 is 1/2.

From compartment 2, there is a way to only compartment 1. Thus, the transition probability from state 2 to state 1 is 1.

From compartment 3, there is a way to compartment 1 and 4. Thus, the transition probability from state 3 to state 1 or state 4 is 1/2.

From compartment 4, there is a way to compartment 3, 5 and 6. Thus, the transition probability from state 4 to state 3, 5 or state 6 is 1/3.

From compartment 5, there is a way to compartment 4 and 6. Thus, the transition probability from state 5 to state 4 or state 6 is 1/2.

From compartment 6, there is a way to compartment 4 and 5. Thus, the transition probability from state 6 to state 4 or state 5 is 1/2.

The one step transition matrix is,

0 1/2 1/2 0 0 0 0 1/2 00 1/2 0 0 0 01/3 0 1/3 1/3 0 00 1/2 0 1/2 0 0 0 1/2 1/2 0

(b)

For, time = 7, the 7-step matrix is,

0 1/2 1/2 0 00 1 0 00 0 0 1/2 0 0 1/2 0 0 0 01/3 0 1/3 1/3 0 00 1/2 0 1/2 0 0 0 1/2 1/2 0

0.006944444 0.252604167 0.36197917 0.08333333 0.14756944 0.14756944 0.505208333 0.000000000 0.01388889 0.32812500 0.07638889 0.07638889 0.361979167 0.006944444 0.04861111 0.32899306 0.126736110.12673611 0.055555556 0.109375000 0.21932870 0.21875000 0.19849537 0.19849537 0.147569444 0.038194444 0.12673611 0.29774306 0.19097222 0.19878472 0.147569444 0.038194444 0.12673611 0.29774306 0.19878472 0.19097222

The transition probability from state 4 to state 6 is 0.19849537

(c)

Let $\pi = \begin{bmatrix} x_1 & x_2 & x_3 & x_4 & x_5 & x_6 \end{bmatrix}$ be the steady state vector (long term distribution of states)

Then,

x1 + x2 + x3 + x4 + x5 + x6 = 1

and  $\pi P = \pi$

or,

0 1/2 1/2 0 0 0 1/2 00 1/2 0 0 0 0 0 1/2 0 1/2 0 0 o 1/21/2 0

which gives,

x2 + x3/2 = x1 --(1)

x1/2 = x2 => x1 = 2x2 --(2)

x1/2 + x4/3 = x3 --(3)

x3/2 + x5/2 + x6/2 = x4 --(4)

x4/3 + x6/2 = x5 --(5)

x4/3 + x5/2 = x6 ---(6)

Subtracting equation 5 and 6, we get

x6/2 - x5/2 = x5 - x6

=> x5 = x6

From (5)

x4/3 + x6/2 = x5 => x4/3 + x6/2 = x6 => x4 / 3 = x6 / 2 => x4 = (3/2)x6  

From (4),

x3/2 + x5/2 + x6/2 = x4 => x3/2 + x6/2 + x6/2 = (3/2)x6 => x3 = x6

From (3),

x1/2 + x4/3 = x3 => x1 / 2 + (1/3)(3/2)x6 = x6 => x1 = x6

From (2),

x1 = 2x2 => x2 = x1/2 = x6/2

Now,

x1 + x2 + x3 + x4 + x5 + x6 = 1

=> x6 + x6/2 + x6 + (3/2)x6 + x6 + x6 = 1

=> (1 + 1/2 + 1 + 3/2 + 1 + 1) x6 = 1

=> 6 x6 = 1

=> x6 = 1/6

The probability that the mouse will be found in compartment 6 at some time n in the far future is 1/6