SDaouki_Discussion10

Exercise 7 page 467

A rat runs through the maze shown in Figure 11.7 (above). 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. (b) Show that it is an ergodic chain but not a regular chain. (c) Find the fixed vector. (d) Find the expected number of steps before reaching Room 5 for the first time, starting in Room 1.

First, The states in this case are rooms 1, 2, 3, 4, 5, and 6. Based on the maze, the transition probabilities will be based on the number of doors of each room:

• Rooms 1 and 2 can only transition to room 3; \(\Rightarrow\) probability = 1

• Room 3 can transition to rooms 1, 2, 4, and 5; each has probability = \(\frac{1}{4}\)

• Room 4 can transition to Rooms 3 and 6; probability = \(\frac{1}{2}\)

• Room 5 can transition to Rooms 3 and 6; probability = \(\frac{1}{2}\)

• Room 6 can transition to Rooms 4 and 5; probability = \(\frac{1}{2}\)

1. The transition matrix P for this Markov chain:

\[ \begin{pmatrix} 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{pmatrix} \]

2. Show that it is an ergodic chain but not a regular chain.

In this chain, it is possible to go from every state (room) to every state (room) (Definition 11.4 page 433), so this chain is ergodic.

3. Find the fixed vector.

To find the fixed vector, we can solve the equation \(wP=w\) with the fact that \(w_1+w_2+w_3+w_4+w_5+w_6=1\)

\[ \begin{pmatrix} w_1 & w_2 & w_3 & w_4 & w_5 & w_6 \end{pmatrix} \times P = \begin{pmatrix} w_1 & w_2 & w_3 & w_4 & w_5 & w_6 \end{pmatrix} \]

\[ \begin{pmatrix} w_1 & w_2 & w_3 & w_4 & w_5 & w_6 \end{pmatrix} \times \begin{pmatrix} 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{pmatrix} = \begin{pmatrix} w_1 & w_2 & w_3 & w_4 & w_5 & w_6 \end{pmatrix} \]

\[ \begin{align*} w_1 \cdot 0 + w_2 \cdot 0 + w_3 \cdot \frac{1}{4} + w_4 \cdot 0 + w_5 \cdot 0 + w_6 \cdot 0 &= w_1 \\ w_1 \cdot 0 + w_2 \cdot 0 + w_3 \cdot \frac{1}{4} + w_4 \cdot 0 + w_5 \cdot 0 + w_6 \cdot 0 &= w_2 \\ w_1 \cdot 1 + w_2 \cdot 1 + w_3 \cdot 0 + w_4 \cdot 1 + w_5 \cdot 1 + w_6 \cdot 0 &= w_3 \\ w_1 \cdot 0 + w_2 \cdot 0 + w_3 \cdot \frac{1}{4} + w_4 \cdot 0 + w_5 \cdot 0 + w_6 \cdot \frac{1}{2} &= w_4 \\ w_1 \cdot 0 + w_2 \cdot 0 + w_3 \cdot \frac{1}{4} + w_4 \cdot 0 + w_5 \cdot 0 + w_6 \cdot \frac{1}{2} &= w_5 \\ w_1 \cdot 0 + w_2 \cdot 0 + w_3 \cdot 0 + w_4 \cdot \frac{1}{2} + w_5 \cdot \frac{1}{2} + w_6 \cdot 0 &= w_6 \\ w_1 + w_2 + w_3 + w_4 + w_5 + w_6 &= 1 \\ \end{align*} \]

Now, let’s solve this system of equation using r-chunk:

# Define the transition matrix
P <- matrix(c(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), nrow = 6, byrow = TRUE)

# Calculate eigenvalues and eigenvectors
eigen_data <- eigen(P)

# Extract eigenvectors corresponding to eigenvalue 1
pi <- eigen_data$vectors[, which(round(eigen_data$values, 5) == 1)]

# Normalize the eigenvector to get the fixed vector
pi <- pi / sum(pi)

# Print the fixed vector
print(pi)

## [1] 0.1666667 0.1666667 0.1666667 0.1666667 0.1666667 0.1666667

The solution I got using the r-code above doesn’t make sense, so based on my understanding and using Example 11.22 on page 440-441, the fixed vector for this chain would be:

\(w= \begin{pmatrix} \frac{1}{12} & \frac{1}{12} & \frac{4}{12} & \frac{2}{12} & \frac{2}{12} & \frac{2}{12} \end{pmatrix}\)

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

To find the expected number of steps, we can use the Mean First Passage Time Equation: \(m_{ij} = 1 + \sum _{k \neq j} p_{ik}m_{ik}\)

So, for room 5: \(m_5=0\) since the room 5 is already reached.

Room 6: \(m_6= 1 + m_{56} m_5 + m_{53} m_4 = 1 + \frac{1}{2} m_5 + \frac{1}{2} m_4=1+ \frac{1}{4} m_4\)

Room 4: \(m_4= 1 + \frac{1}{2} m_6 + \frac{1}{2} m_3\)

Room 3: \(m_3= 1 + \frac{1}{4} m_1 + \frac{1}{4} m_2+ \frac{1}{4} m_4 +\frac{1}{4} m_5=1 + \frac{1}{4} m_1 + \frac{1}{4} m_2+ \frac{1}{4} m_4\)

Room 1: \(m_1= 1 +m_3\)

Room 2: \(m_2= 1 +m_3\)

After a long calculations (by hand) to solve the above system of equation, I found that \(m_1= \frac{32}{5} \approx 6\)