11.5 Problem 7

A rat runs through the maze shown in Figure 11.7. At each step it leaves the room it is in by choosing at random one of the doors out of the room.

A

**Give the transition matrix P for this Markov chain

\[P = \left[ \begin{array}{cccccc} 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 \\ 1/4 & 1/4 & 0 & 1/4 & 1/4 & 0 \\ 0 & 0 & 1/2 & 0 & 0 & 1/2 \\ 0 & 0 & 1/2 & 0 & 0 & 1/2 \\ 0 & 0 & 0 & 1/2 & 1/2 & 0 \ \end{array} \right] \]

B

It is ergodic because you can go from any state to any other state. It is not regular because you cannot move to certain states if there is an odd power on certain elements of the transition matrix. For example, you cannot move from state 1 back to state 1 in odd number of steps

C

Easy way to find the fixed vector is to count the number of ways a state can travel to another state (How many doors the room has).

\(x = (1, 1, 4, 2, 2, 2)\)

The normalize it:

\(w = (\frac{1}{12}, \frac{1}{12}, \frac{1}{3}, \frac{1}{6}, \frac{1}{6}, \frac{1}{6},)\)

D

Put the transitional matrix in canonical form. Since we’re moving from State 1 to State 5, State 5 is an absorbsion state so we remove it from the matrix, leaving us with matrix Q.

\[Q = \left[ \begin{array}{ccccc} 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 1/4 & 1/4 & 0 & 1/4 & 0 \\ 0 & 0 & 1/2 & 0 & 1/2 \\ 0 & 0 & 1/2 & 0 & 1/2 \\ 0 & 0 & 0 & 1/2 & 0 \ \end{array} \right] \] \[N = I-Q = \left[ \begin{array}{ccccc} 1 & 0 & 0 & 1 & 0 \\ 0 & 1 & 1 & 0 & 0 \\ 1/4 & 1/4 & 1 & 1/4 & 0 \\ 0 & 0 & 1/2 & 1 & 1/2 \\ 0 & 0 & 0 & 1/2 & 1 \ \end{array} \right] \]

\(N^{-1}\) =

mat <- matrix(c(1,0,0,1,0,0,1,1,0,0,.25, .25, 1, .25,0,0,0,.5,1,.5,0,0,0,.5,1), nrow = 5, ncol = 5, byrow = T)

inv_mat <- solve(mat)
inv_mat
##            [,1]       [,2]       [,3]       [,4]       [,5]
## [1,]  0.7777778 -0.2222222  0.8888889 -1.3333333  0.6666667
## [2,]  0.3333333  1.3333333 -1.3333333  0.0000000  0.0000000
## [3,] -0.3333333 -0.3333333  1.3333333  0.0000000  0.0000000
## [4,]  0.2222222  0.2222222 -0.8888889  1.3333333 -0.6666667
## [5,] -0.1111111 -0.1111111  0.4444444 -0.6666667  1.3333333

\(t = Nc\) where \(t\) is the expected number of steps before it is absorbed. \(c\) is a column vectors of ones.

c <- matrix(c(1, 1, 1, 1, 1), ncol = 1)

t <- inv_mat %*% c
t
##           [,1]
## [1,] 0.7777778
## [2,] 0.3333333
## [3,] 0.6666667
## [4,] 0.2222222
## [5,] 0.8888889

From the result, the expected number of steps is .77 from State 1 until it is absorbed into State 5. This obviously isn’t right since it takes a minimum of two steps to get from state one to state 5.