---
title: "4.1 Markov Chains"
format:
  html:
    self-contained: TRUE
---

![](https://colleen.quarto.pub/ddc_workbook/images/lemons.png){width=50%}

## Introduction

In assignment 3.1, we built a rudimentary understanding of the "discrete choice" part of the Dynamic Discrete Choice (DDC) topic. In this assignment and the next two, I'll build the "dynamic" part. 

I'll begin this assignment 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 transitions from one state to another based on specific probabilistic rules. Its key feature is that the future state depends only on the current state, regardless of how the process reached that point. In other words, the possible future states are determined solely by the present state, not by the sequence of events that preceded it.

## 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.

### Rows and Columns of a Matrix

[Khan Academy: Intro to Matrices](https://www.khanacademy.org/math/precalculus/x9e81a4f98389efdf:matrices/x9e81a4f98389efdf:mat-intro/a/intro-to-matrices?modal=1)

<p style="background-color:#e6c3e8; border-width:3px; border-style:solid; border-color:#e6c3e8; padding: 1em;">
**Exercise 1:** What are the dimensions of this matrix?
\begin{equation}
\begin{bmatrix}
1 & 2 & 3\\
4 & 5 & 6
\end{bmatrix}
\end{equation}
</p>

### Multiplying a Matrix by a Scalar

[Khan Academy: Scalar Multiplication](https://www.khanacademy.org/math/precalculus/x9e81a4f98389efdf:matrices/x9e81a4f98389efdf:multiplying-matrices-by-scalars/v/scalar-multiplication?modal=1)

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:

```{r}
matrix(
    1:6,
    nrow = 2,
    byrow = T
)
```

You can multiply a scalar and a matrix using the `*` operator:

```{r}
2 * matrix(1:6, nrow = 2, byrow = T)
```

<p style="background-color:#e6c3e8; border-width:3px; border-style:solid; border-color:#e6c3e8; padding: 1em;">
**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}
</p>

### Matrix Addition

[Khan Academy: Matrix Addition and Subtraction](https://www.khanacademy.org/math/precalculus/x9e81a4f98389efdf:matrices/x9e81a4f98389efdf:adding-and-subtracting-matrices/v/matrix-addition-and-subtraction-1?modal=1)

<p style="background-color:#e6c3e8; border-width:3px; border-style:solid; border-color:#e6c3e8; padding: 1em;">
**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}
</p>

### Matrix Multiplication

[Khan Academy: Intro to Matrix Multiplication](https://www.khanacademy.org/math/precalculus/x9e81a4f98389efdf:matrices/x9e81a4f98389efdf:multiplying-matrices-by-matrices/v/matrix-multiplication-intro?modal=1)

[Check your understanding on Matrix Multiplication](https://www.khanacademy.org/math/precalculus/x9e81a4f98389efdf:matrices/x9e81a4f98389efdf:multiplying-matrices-by-matrices/a/multiplying-matrices?modal=1)

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:

```{r}
matrix(1:4, nrow = 2, byrow = T) * matrix(-1:2, nrow = 2, byrow = T)
```

To do proper **matrix multiplication** in R, there is a different operator: `%*%`

```{r}
matrix(1:4, nrow = 2, byrow = T) %*% matrix(-1:2, nrow = 2, byrow = T)
```

<p style="background-color:#e6c3e8; border-width:3px; border-style:solid; border-color:#e6c3e8; padding: 1em;">
**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}
</p>

<p style="background-color:#e6c3e8; border-width:3px; border-style:solid; border-color:#e6c3e8; padding: 1em;">
**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}
</p>

## 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.

<p style="background-color:#e6c3e8; border-width:3px; border-style:solid; border-color:#e6c3e8; padding: 1em;">
**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?
</p>

<p style="background-color:#e6c3e8; border-width:3px; border-style:solid; border-color:#e6c3e8; padding: 1em;">
**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?
</p>

Let's also suppose that the 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.

<p style="background-color:#e6c3e8; border-width:3px; border-style:solid; border-color:#e6c3e8; padding: 1em;">
**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?
</p>

<p style="background-color:#e6c3e8; border-width:3px; border-style:solid; border-color:#e6c3e8; padding: 1em;">
**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?
</p>

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.

![](https://colleen.quarto.pub/ddc_workbook/images/transition.jpeg)

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:

```{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)
```

But 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:

```{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)
```

But 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!

<p style="background-color:#e6c3e8; border-width:3px; border-style:solid; border-color:#e6c3e8; padding: 1em;">
**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.
</p>

## 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}

<p style="background-color:#e6c3e8; border-width:3px; border-style:solid; border-color:#e6c3e8; padding: 1em;">
**Exercise 11:** Interpret $P_{harvest}$ and explain why the probability transition matrix has the column of 1's and the rest 0's.
</p>

So for example, if I start with 2 lemons, I harvest, then I water, here's the probabilities of where I'll end up:

```{r}
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)
```

I'll continue this discussion of Markov Decision Processes (MDP's) in the next assignment.
