This post features a simple example of a Markov chain. Markov chains are used in mathematical modeling to model process that “hop” from one state to the other. They are used in computer science, finance, physics, biology, you name it! A relevant example to almost all of us are the “suggestions” you get when typing a search in to Google or when typing text in your smartphone. Yep, those use Markov chains. To get an idea how they work, consider the following problem:

Consider a model for the long-term dining choices of students at Valley University. It is found that 25% of the students who eat at the university’s Gilcrest Dining Hall will return to eat there again, whereas those who eat at Schilling Dining Hall have a 93% return rate. These are the only two dining halls on campus and all students eat at one of these halls. What is the percentage of students eating at each hall in the long run?

This problem describes a Markov chain with two states, namely Gilcrest Dining Hall and Schilling Dining Hall. Before diving into solving the problem, let’s look at it visually:

From the diagram here, you can see how the process “hops” between the two states. In one state, a certain number of students are at Gilcrest, and the rest are at Schilling. In the next state, 75% of the Gilcrest students “hop” over to Schilling, and the rest stay where they are. For the Schilling students, only 7% “hop” over to Gilcrest, and the rest stay put.

We can come up with some equations that model this process as well. Let \(G_n\) denote the number of students eating at Gilcrest at time \(n\), and \(S_n\) the number of students eating at Schilling at time \(n\). Then, the number of students eating at each dining hall in the next state is given by \(G_{n+1}\) and \(S_{n+1}\), and we can write

\begin{array}{c c}

G_{n+1} &= .25G_n + .07S_n \\

S_{n+1} &= .75G_n + .93S_n

\end{array}

Where do these equations come from? Well, if \(G_n\) are the amount of students eating at Gilcrest on day \(n\), then 25% of those will eat at Gilcrest the next day, \(G_{n+1}\). This amount is represented by the quantity \(.25 G_n\). Similarly, 7% of students eating at Schilling on day \(n\) will go to Gilcrest the next day. This amount is \(.07 S_n\). These two amounts added together then give us the total number of students eating at Gilcrest on day \(n+1\).

We can go a step further and can write the above equation as a matrix equation:

\begin{equation*}

\begin{bmatrix}

G_{n+1} \\ S_{n+1}

\end{bmatrix}

=

\begin{bmatrix}

.25 & .07 \\ .75 & .93

\end{bmatrix}

\begin{bmatrix}

G_n \\ S_n

\end{bmatrix}

\end{equation*}

The matrix in this equation is called a * transition matrix *. The vectors are called * state vectors *.

What’s cool about the transition matrix is that we can multiply it by any state vector to get the next state. So for instance, suppose that on Day 0, all of the students eat at Gilcrest. This would correspond to the following initial state vector:

\begin{equation*}

\begin{bmatrix} G_0 \\ S_0 \end{bmatrix}

=

\begin{bmatrix} 1 \\ 0 \end{bmatrix}

\end{equation*}

To figure out where the students will eat on Day 1, just multiply this vector by the transition matrix.

\begin{equation*}

\begin{bmatrix}

.25 & .07 \\ .75 & .93

\end{bmatrix}

\begin{bmatrix} 1 \\ 0 \end{bmatrix}

=

\begin{bmatrix} .25 \\ .75 \end{bmatrix}

=

\begin{bmatrix} G_1 \\ S_1 \end{bmatrix}

\end{equation*}

So on Day 1, 25% of the students eat at Gilcrest, and 75% eat at Schilling.

We can keep multiplying by the transition matrix to find the behavior of students on subsequent days. For Day 2, we get

\begin{equation*}

\begin{bmatrix}

.25 & .07 \\ .75 & .93

\end{bmatrix}

\begin{bmatrix} .25 \\ .75 \end{bmatrix}

=

\begin{bmatrix} .115 \\ .885 \end{bmatrix}

=

\begin{bmatrix} G_2 \\ S_2 \end{bmatrix}

\end{equation*}

Neat. We can keep doing this for as long as we like. I ran the model for 10 days (or states) and graphed the result.

We can see from this that it only takes a few days to reach the * steady state *. The steady state is the state where the proportion of students eating at each dining hall no longer changes. For this problem, we hit it (exactly) at around Day 12. The long term behavior is approximately 8.5% of students eat at Gilcrest, and 91.5% eat at Schilling.

#### Markov Chain Example – 3 States

Now, if you’re like me, you’re probably thinking the above formulation is a bit contrived. After all, by the time you figure out the eating habits of the students, wouldn’t we have already reached the steady state? Well, yes, it’s true, this example is completely contrived, but it illustrates the point. To make it more interesting though, we could shake things up a bit by posing the following question: What would the long-term dining behavior be if we added an on-campus pizza delivery service?

To answer this question, suppose we surveyed the students, asking them how their dining habits would change if there was an on-campus pizza delivery option. Suppose we got the following:

\(G_{n+1}\) | \(S_{n+1}\) | \(P_{n+1}\) | |
---|---|---|---|

\(G_n\) | .25 | .25 | .50 |

\(S_n\) | .10 | .30 | .60 |

\(P_n\) | .05 | .15 | .80 |

So for example, 50% of the students eating at Gilcrest at stage \(n\) will choose pizza at stage \(n+1\). In picture form, we get

Our matrix equation looks like this:

\begin{equation*}

\begin{bmatrix}

G_{n+1} \\ S_{n+1} \\ P_{n+1}

\end{bmatrix}

=

\begin{bmatrix}

.25 & .10 & .05 \\ .10 & .30 & .60 \\ .50 & .60 & .80

\end{bmatrix}

\begin{bmatrix}

G_n \\ S_n \\ P_n

\end{bmatrix}

\end{equation*}

I chose my initial state to be where we left off in the previous problem, namely

\begin{equation*}

\begin{bmatrix}

G_0 \\ S_0 \\ P_0

\end{bmatrix}

=

\begin{bmatrix}

.085 \\ .915 \\ 0

\end{bmatrix}

\end{equation*}

I ran the simulation for 10 days again and got the following graph.

Wow. The Schilling dining hall has met its match. Gilcrest enjoyed a slight bump in popularity in the beginning, but then dropped again, ending at 7.4% in the steady state. Schilling ended up at 18.5%, and the pizza delivery enjoys a whopping 74% popularity. (If you’re wondering why these don’t quite add up to 100%, it’s because I rounded). So if the college wants to keep its revenue from the dining halls up, I would recommend that they not allow an on-campus pizza delivery service.