Markov Chains

Part 1: Matrices

Question 1: Matrix Dimensions

A matrix has dimensions “rows × columns.” What are the dimensions of the matrix below?

\[ A = \begin{bmatrix} 2 & 5 & 7 \\ 0 & 1 & 4 \end{bmatrix} \]

Question 2: Scalar multiplication

Let matrix B be defined as:

\[ B = \begin{bmatrix} 1 & -2 \\ 3 & 0 \end{bmatrix} \]

Compute \(3B\) by hand, then verify your answer in R.

B <- matrix(
  c(1, -2, 3,  0),
  nrow = 2, byrow = TRUE
  )

___ * B

Question 3: Create a matrix in R

Create the following matrix in R and store it as C.

\[ C = \begin{bmatrix} 0.75 & 0.25 \\ 0.4 & 0.60 \end{bmatrix} \]

C <- matrix(
  ___
)

Part 2: Matrix Algebra

Question 4: Matrix Addition

Let A and D be:

\[ A = \begin{bmatrix} 2 & 1 \\ -1 & 3 \end{bmatrix}, \quad D = \begin{bmatrix} 0 & 4 \\ 5 & -2 \end{bmatrix} \]

Compute A + D by hand, and then verify your answer in R.

A <- matrix(___)

D <- matrix(___)

___ + ___

Question 5: Matrix Addition

Reflect: is it possible to add a 2x2 matrix to a 2x3 matrix? What restrictions exist for matrix addition?

Question 6: Matrix Multiplication

Matrix multiplication works by taking the dot product of rows from the first matrix with columns from the second matrix.

For example, to compute:

\[ A \times D = \begin{bmatrix} 2 & 1 \\ -1 & 3 \end{bmatrix} \times \begin{bmatrix} 0 & 4 \\ 5 & -2 \end{bmatrix} \]

• To compute the entry in row 1, column 1, take row 1 of A and column 1 of D: (2)(0) + (1)(5) = 5
• To compute the entry in row 1, column 2, take row 1 of A and column 2 of D: (2)(4) + (1)(-2) = 6
• To compute the entry in row 2, column 1, take row 2 of A and column 1 of D: (-1)(0) + (3)(5) = 15
• To compute the entry in row 2, column 2, take row 2 of A and column 2 of D: (-1)(4) + (3)(-2) = -10

Final answer:

\[ AD = \begin{bmatrix} 5 & 6 \\ 15 & -10 \end{bmatrix} \]

Verify this result in R using the matrix multiplication operator %*%.

Question 7: Matrix Multiplication

Matrices do not need to have the same dimensions in order for matrix multiplication to be defined. As long as the number of columns in the first matrix is equal to the number of rows in the second, you can multiply the two matrices.

Let \(u = [0.3, 0.7]\). Compute \(uA\) by hand and then in R.

matrix(___) %*% A

Part 3: Markov Chains

A Markov Chain is a mathematical system that experiences transitions from one state to another according to certain probabilistic rules. The defining characteristic of a Markov chain is that no matter how the process arrived at its present state, the possible future states are fixed.

For example: consider a town with two restaurants: a pizza place and a Mexican restaurant.

A study found the following patterns:

• Of those who eat at the pizza place in a given week, 75% return to the pizza place the following week, and 25% go to the Mexican restaurant the following week.
• Of those who eat at the Mexican restaurant in a given week, 40% go to the pizza place the following week, and 60% return to the Mexican restaurant the following week.

There are two possible states: Pizza; Mexican.

The transition matrix is a matrix that defines transition probabilities between states, where rows define the current restaurant and columns define next week’s restaurant.

\[ P = \begin{bmatrix} 0.75 & 0.25 \\ 0.40 & 0.60 \end{bmatrix} \]

Question 8: Transition Matrix

Write R code to create matrix P.

P <- ___

The first row [.75, .25] means that if someone gets pizza this week, there’s a 75% chance they get pizza next week and a 25% chance they get Mexican next week.

The second row [.4, .6] means that if someone gets Mexican this week, there’s a 40% chance they get pizza next week and a 60% chance they get Mexican next week.

This is a Markov chain because where someone eats next week depends only on where they ate this week, not on earlier weeks. The current state contains all relevant information.

Suppose someone gets pizza this week. Then their state vector is: \(u = [1, 0]\).

Question 9: Prediction in 1 week

Multiply u by the transition matrix P to get the prediction about where they’ll eat next week:

\[ uP = \begin{bmatrix} 1 & 0 \end{bmatrix} \begin{bmatrix} 0.75 & 0.25 \\ 0.40 & 0.60 \end{bmatrix} \]

matrix(___) %*% P

Question 10: Population interpretation

If 100 people get pizza this week, how many people will get pizza next week and how many will get Mexican next week?

Now consider: what will happen 2 weeks from now? If 100 people get pizza this week and 0 get Mexican, how many people are getting pizza versus Mexican in 2 weeks?

\[ \begin{bmatrix} .75 & .25 \end{bmatrix} \cdot \begin{bmatrix} 0.75 & 0.25 \\ 0.40 & 0.60 \end{bmatrix} = \begin{bmatrix} 0.6625 & 0.3375 \end{bmatrix} \]

Notice another way to write this is:

\[ \begin{bmatrix} 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} 0.75 & 0.25 \\ 0.40 & 0.60 \end{bmatrix} \cdot \begin{bmatrix} 0.75 & 0.25 \\ 0.40 & 0.60 \end{bmatrix} = \begin{bmatrix} 0.6625 & 0.3375 \end{bmatrix} \]

That is, you can find what happens \(n\) weeks in the future by calculating:

\[ \begin{bmatrix} 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} 0.75 & 0.25 \\ 0.40 & 0.60 \end{bmatrix}^n \]

Question 11: Long-Run Equilibrium

Given 100 people get pizza this week and 0 get Mexican, how many people are getting pizza versus Mexican in 1 year (52 weeks)? Use the matrix exponent operator %^% from the package expm.

install.packages("expm")

library(expm)

matrix(___) %*% (___ %^% 52)

Notice that if you take the transition matrix P and raise it to a large enough power, both rows are identical:

(P %^% 52)

This is the long-run equilibrium: it doesn’t matter how many people start where, they converge to getting pizza and Mexican at this rate.

Part 4: Transition Matrix to replace move() in GridWorld

Our GridWorld game is another example of a Markov process because the next state depends only on the current state and the action taken there, not how the agent arrived at the current state.

We’ve been using a function move(cell, action) to define movement around the grid, but we could also use transition matrices to do the same task. Here’s how:

\(P^{east}\) is the transition matrix where the \((i, j)\) entry equals 1 if taking action “east” from cell i lands you in cell j, and 0 otherwise.

Note that the sum of each row in any transition matrix must always equal 1: given any state, the sum of the probabilities you land in any other next state must always equal 1.

P_east <- matrix(rep(0, 81), nrow = 9)

P_east[1, 2] <- 1
P_east[2, 3] <- 1
P_east[3, 3] <- 1 # boundary
P_east[4, 5] <- 1
P_east[5, 6] <- 1
P_east[6, 6] <- 1 # boundary
P_east[7, 8] <- 1
P_east[8, 9] <- 1
P_east[9, 9] <- 1 # boundary

# Check
all(rowSums(P_east) == rep(1, 9))

Question 12: Define P_south

P_south <- ___

# Check
all(rowSums(P_south) == rep(1, 9))

Question 13: Check

If an agent’s starting position is cell 1 (u = [1, 0, 0, 0, 0, 0, 0, 0, 0]), use P_east and P_south to verify that they end up in cell 9 when they go east twice and then south twice.

u <- matrix(___)

u %*% (___) %*% (___)

Download this assignment

Here’s a link to download this assignment.