pg.467 11.5.7

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.

\[\mathbf{P} = \left(\begin{array} {rrr} 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 \\ \frac{1}{4} & \frac{1}{4} & 0 & \frac{1}{4} & \frac{1}{4} & 0 \\ 0 & 0 & \frac{1}{2} & 0 & 0 & \frac{1}{2} \\ 0 & 0 & \frac{1}{2} & 0 & 0 & \frac{1}{2}\\ 0 & 0 & 0 & \frac{1}{2} & \frac{1}{2} & 0 \end{array}\right)\]

P = matrix(c(0 , 0 , 1 , 0 , 0 , 0,0 , 0 , 1 , 0 , 0 , 0,.25,.25, 0 , .25 , .25 ,  0,0 , 0 , .5 , 0 , 0 , .5,0 , 0 , .5 , 0  , 0 , .5,0 , 0 , 0 , .5 , .5 , 0), nrow=6,ncol=6,byrow = TRUE)

(b) Show that it is an ergodic chain but not a regular chain.

The chain is ergodic because it is possible to go from any state (room) to any other state. There is no methond in which, if the rat was to start in any room, it would find itself with no way out. In terms of the matrix P, there is no zero row.

It is also not a regular chain because when we raise P to the second power, we have non-positive entries (zero).

P%*%P
##       [,1]  [,2] [,3]  [,4]  [,5] [,6]
## [1,] 0.250 0.250 0.00 0.250 0.250 0.00
## [2,] 0.250 0.250 0.00 0.250 0.250 0.00
## [3,] 0.000 0.000 0.75 0.000 0.000 0.25
## [4,] 0.125 0.125 0.00 0.375 0.375 0.00
## [5,] 0.125 0.125 0.00 0.375 0.375 0.00
## [6,] 0.000 0.000 0.50 0.000 0.000 0.50

(c) Find the fixed vector.

R1 = R3

R2 = R3

R3 = .25(R1)+.25(R2)+.25(R4)+.25(R5)

R4 = .5(R3)+.5(R6)

R5 = .5(R3)+.5(R6)

R6 = .5(R4)+.5(R5)

1 = R1+R2+R3+R4+R5+R6

Solve for the variables to get:

(R1 R2 R3 R4 R5 R6) = (0.083, 0.083, 0.333, 0.167, 0.167, 0.167)

Note: apparently, the fixed row vector can be considersed as a left eigenvector, but I had little success with finding the right values as seen below

# to find left eigenvector, transpose matrix
w = round(eigen(t(P))$values,4)

# divide vector by sum of components
for(i in 1:dim(P)[1]){
  w[i] = w[i]/sum(P[,i])
}
w
## [1]  4.0000000 -4.0000000  0.1666667 -0.6666667  0.0000000  0.0000000

(d) Find the expected number of steps before reaching Room 5 for the first time, starting in Room 1.

s(i) = E(number of steps until R5|X0=i) #in this case our X0 is room 1

s(5) = 0

s(6) = 1+ .5s(5)+ .5s(4)

s(4) = 1+ .5s(6)+ .5s(3)

s(3) = 1+ .25s(1)+ .25s(2)+ .25s(4)+ .25s(5)

s(2) = 1+ s(3)

s(1) = 1+ s(3)