matrix(
1:6,
nrow = 2,
byrow = T
) [,1] [,2] [,3]
[1,] 1 2 3
[2,] 4 5 63 Markov Chains
3.1 Introduction
In the previous two chapters, I built a rudimentary understanding of the “discrete choice” part of the DDC topic. In this chapter and the next, I’ll build the “dynamic” part.
I’ll begin this chapter with a matrix algebra review, and then I’ll introduce an example of a markov chain. A markov chain is a simple but powerful tool to think about stochastic dynamic systems.
Definition: Markov Chain. “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.” – Maltby, Pakornrat, and Jackson (2022)
3.2 Matrix Algebra
Khan Academy has a great intro to matrix algebra, so I’ll outsource this part. Click on the Khan Academy links to learn about the subject and then come back here to do the exercises.
3.2.1 Rows and Columns of a Matrix
Khan Academy: Intro to Matrices
Exercise 1: What are the dimensions of this matrix? \[\begin{equation} \begin{bmatrix} 1 & 2 & 3\\ 4 & 5 & 6 \end{bmatrix} \end{equation}\]
3.2.2 Multiplying a Matrix by a Scalar
Khan Academy: Scalar Multiplication
Here’s how you can define a matrix in R. Here I tell matrix() that the data are the numbers 1 through 6, I want there to be 2 rows, and I want the data to be filled in by row instead of by column:
You can multiply a scalar and a matrix using the * operator:
2 * matrix(1:6, nrow = 2, byrow = T) [,1] [,2] [,3]
[1,] 2 4 6
[2,] 8 10 12
Exercise 2: Write R code to create this matrix using the matrix() function: \[\begin{equation}
\begin{bmatrix}
1 & 0 & 1\\
0 & 1 & 0\\
1 & 0 & 1
\end{bmatrix}
\end{equation}\]
3.2.3 Matrix Addition
Khan Academy: Matrix Addition and Subtraction
Exercise 3: Solve for x, y, and z. \[\begin{equation} \begin{bmatrix} x & 0 & 1\\ 0 & 1 & y\\ 1 & z & 1 \end{bmatrix} + \begin{bmatrix} 1 & 1 & 1\\ 0 & 1 & 1\\ 0 & 0 & 1 \end{bmatrix} = \begin{bmatrix} -1 & 1 & 2\\ 0 & 2 & 1\\ 1 & 4 & 2 \end{bmatrix} \end{equation}\]
3.2.4 Matrix Multiplication
Khan Academy: Intro to Matrix Multiplication
Check your understanding on Matrix Multiplication
In R, if you use the standard multiplication operator *, it will multiply matrices “element-by-element”. That is if you use *:
\[\begin{equation} \begin{bmatrix} 1 & 2\\ 3 & 4 \end{bmatrix} \begin{bmatrix} -1 & 0\\ 1 & 2 \end{bmatrix} \end{equation}\]
Evalutes to be:
matrix(1:4, nrow = 2, byrow = T) * matrix(-1:2, nrow = 2, byrow = T) [,1] [,2]
[1,] -1 0
[2,] 3 8To do proper matrix multiplication in R, there is a different operator: %*%
matrix(1:4, nrow = 2, byrow = T) %*% matrix(-1:2, nrow = 2, byrow = T) [,1] [,2]
[1,] 1 4
[2,] 1 8
Exercise 4: Solve for x and y using matrix multiplication. You can check your work in R using the matrix multiplication operator %*%. \[\begin{equation}
\begin{bmatrix}
2 & 0 \\
1 & 1
\end{bmatrix}
\begin{bmatrix}
1 & 2\\
0 & -1
\end{bmatrix}
=
\begin{bmatrix}
x & 4\\
1 & y
\end{bmatrix}
\end{equation}\]
Exercise 5: Again, solve for x and y using matrix multiplication. Note that matrices do not have to have the same dimensions in order to be conformable by matrix multiplication. \[\begin{equation} \begin{bmatrix} x & y \end{bmatrix} \begin{bmatrix} 1 & 2\\ 0 & -1 \end{bmatrix} = \begin{bmatrix} 2 & 5 \end{bmatrix} \end{equation}\]
3.3 Probability Transition Matrices
Suppose you have a small lemon tree. If you water it, then each period, 0-2 new lemons might appear on it (a period could be days, weeks, months: however long you think it takes for lemons to grow).
New lemons grow on the tree with some known probability. Let’s say that 0 new lemons grow from one period to the next 60% of the time. One new lemon grows 30% of the time, and two new lemons grow 10% of the time.
Exercise 6: Suppose that in period 1, you have 0 lemons on the tree. What is the probability you’ll have 0, 1, and 2 lemons on the tree in period 2?
Exercise 7: Suppose that in period 1, you have 1 lemon on the tree. What is the probability you’ll have 0, 1, 2, and 3 lemons on the tree in period 2?
Let’s also suppose that the small lemon tree has a maximum number of lemons, and that maximum is 3. Once the lemon tree has 3 lemons on it, it will stop growing new lemons.
Exercise 8: Suppose that in period 1, you have 2 lemons on the tree. What is the probability you’ll have 0, 1, 2, and 3 lemons on the tree in period 2?
Exercise 9: Suppose that in period 1, you have 3 lemons on the tree. What is the probability you’ll have 0, 1, 2, and 3 lemons on the tree in period 2?
Now I’ll put the probabilities you found in exercises 6-9 into something called a probability transition matrix. The rows refer to how many lemons are on the tree this period, and the columns refer to how many lemons might be on the tree next period. The elements of the matrix are corresponding probabilities.
The way you want to read a probability transition matrix is across the rows. For instance, the first row reads: if you have 0 lemons this period, then next period, the probability you’ll have 0 lemons is 0.6, the probability you’ll have 1 lemon is .3, the probability you’ll have 2 lemons is .1, and the probability you’ll have 3 lemons is 0. You can read the other rows in a similar way. The probability transition matrix tells you the probabilities you’ll transition from any one state (number of lemons on the tree) to any other state, from one period to the next.
If I let the vector (1, 0, 0, 0) indicate we’re in the state with 0 lemons, notice how matrix multiplication of the state vector and the probability transition matrix outputs the probabilities I’ll be in each state next period. This is of course not surprising because left multiplication by a unit vector like this just selects the first row.
\[\begin{equation} \begin{bmatrix} 1 & 0 & 0 & 0 \end{bmatrix} \begin{bmatrix} .6 & .3 & .1 & 0\\ 0 & .6 & .3 & .1\\ 0 & 0 & .6 & .4\\ 0 & 0 & 0 & 1 \end{bmatrix} = \begin{bmatrix} .6 & .3 & .1 & 0 \end{bmatrix} \end{equation}\]
Checking our work in R:
matrix(c(1, 0, 0, 0), nrow = 1) %*%
matrix(c(.6, .3, .1, 0,
0, .6, .3, .1,
0, 0, .6, .4,
0, 0, 0, 1),
nrow = 4, byrow = T) [,1] [,2] [,3] [,4]
[1,] 0.6 0.3 0.1 0But what’s really interesting is that I can right-multiply by the probability transition matrix again and get the probability I’ll end up in each state in 2 periods instead of just one! For example, what’s the probability that, if I start with 0 lemons, I’ll still have 0 lemons after 2 periods?
\[\begin{equation} \begin{bmatrix} 1 & 0 & 0 & 0 \end{bmatrix} \begin{bmatrix} .6 & .3 & .1 & 0\\ 0 & .6 & .3 & .1\\ 0 & 0 & .6 & .4\\ 0 & 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} .6 & .3 & .1 & 0\\ 0 & .6 & .3 & .1\\ 0 & 0 & .6 & .4\\ 0 & 0 & 0 & 1 \end{bmatrix} = \begin{bmatrix} .36 & .36 & .21 & .07 \end{bmatrix} \end{equation}\]
Reading the first entry of the output, it’s 0.36: to end up with 0 lemons after 2 periods, I’d need to not grow any lemons in the first period (which happens with probability 0.6) and then not grow any lemons in the second period (w.p. 0.6). So the joint probability is \(0.6 * 0.6 = .36\).
Checking my work in R:
matrix(c(1, 0, 0, 0), nrow = 1) %*%
matrix(c(.6, .3, .1, 0,
0, .6, .3, .1,
0, 0, .6, .4,
0, 0, 0, 1),
nrow = 4, byrow = T) %*%
matrix(c(.6, .3, .1, 0,
0, .6, .3, .1,
0, 0, .6, .4,
0, 0, 0, 1),
nrow = 4, byrow = T) [,1] [,2] [,3] [,4]
[1,] 0.36 0.36 0.21 0.07But you don’t have to stop there: you can continue right-multiplying by the probability transition matrix to get the probabilities you’ll end up in each state after 3, 4, 5, or more periods!
Exercise 10: Suppose you have 0 lemons on the tree in period 1. What are the probabilities you’ll have 0, 1, 2 and 3 lemons on the tree in period 5? You can use R to do this calculation.
3.4 Actions in a Markov Decision Process
My lemon tree markov chain example is coming along nicely, but you may be wondering: when do we harvest the lemons? And how do we represent that? The answer is with actions.
Suppose there are two actions available: water and harvest. If I choose to water, the lemon tree process will evolve just like in the previous sections, with this probability transition matrix:
\[\begin{equation} P_{water} = \begin{bmatrix} .6 & .3 & .1 & 0\\ 0 & .6 & .3 & .1\\ 0 & 0 & .6 & .4\\ 0 & 0 & 0 & 1 \end{bmatrix} \end{equation}\]
But if I choose to harvest the lemons, I pick all the lemons on the tree and no new lemons grow, so I end up with 0 lemons on the tree the next period. To capture this transition, there is a different probability transition matrix:
\[\begin{equation} P_{harvest} = \begin{bmatrix} 1 & 0 & 0 & 0\\ 1 & 0 & 0 & 0\\ 1 & 0 & 0 & 0\\ 1 & 0 & 0 & 0 \end{bmatrix} \end{equation}\]
Exercise 11: Interpret \(P_{harvest}\) and explain why the probability transition matrix has the column of 1’s and the rest 0’s.
So for example, if I start with 2 lemons, I harvest, then I water, here’s the probabilities of where I’ll end up:
matrix(c(0, 0, 1, 0), nrow = 1) %*%
matrix(c(1, 0, 0, 0,
1, 0, 0, 0,
1, 0, 0, 0,
1, 0, 0, 0),
nrow = 4, byrow = T) %*%
matrix(c(.6, .3, .1, 0,
0, .6, .3, .1,
0, 0, .6, .4,
0, 0, 0, 1),
nrow = 4, byrow = T) [,1] [,2] [,3] [,4]
[1,] 0.6 0.3 0.1 0I’ll continue this discussion of Markov Decision Processes (MDP’s) in the next chapter.
3.5 Programming Exercises
Exercise 12: Complete project Euler problem 3: Largest prime factor.
3.6 References
Khan (2022): Matrices chapter from Khan Academy
Maltby, Pakornrat, and Jackson (2022): Markov Chains