Markov Chains and State Diagrams

Jacob Paltrowitz

Introduction

A state diagram is a visual representation of the behavior of a system. The diagram takes certain input states and returns output states. State diagrams are very commonly used in computer science, as machines can identify inputs to create outputs. This article will focus on a certain type of state diagram called a Markov Chain.

Markov Chains are special in a few ways. They have no “memory," meaning the output for time \(t=n\) is determined solely by the state at \(t=n-1\). They are probabilistic, so there are fixed probabilities to determine the chances of going to certain states. This means for a certain chain, we can write out the probability of going from every state to every other state. We could represent this data in a drawn out diagram. Let’s make a Markov Chain for the following problem: In tennis, players can reach a score of deuce, where a player needs to win two more points than their opponent in order to win the game. Let’s calculate the probability of player 1 winning after three moves starting at deuce, given that they win \(\frac{2}{3}\) of the points. The diagram would look like:

Tennis game state diagram
We start at the central "Deuce," and proceed along the chain according to the probabilistic rules. We could set up equations for each of the states and use algebra to solve. However, there is an easier way. We can store the information in a matrix, like the one below, and use that to assist our solving.

\(\begin{bmatrix} P_{11} & P_{12} & P_{13} & \dots & P_{1n} \\ P_{21} & P_{22} & P_{23} & \dots & P_{2n} \\ P_{31} & P_{32} & P_{33} & \dots & P_{3n} \\ \vdots & \vdots & \vdots & \ddots & \vdots\\ P_{n1} & P_{n2} & P_{n3} & \dots & P_{nn} \end{bmatrix}\)

In the matrix, entry \(P_{ij}\). represents the probability of going to state \(j\), given that we are at state \(i\). So the first entry in the upper left is he probability of staying at state 1 once we are at state 1. We can make some key observations about this matrix. Since probabilities must sum to 1, each row must sum to 1. This is called a stochastic matrix.

Operating on Matrices

As we are going to use matrices, it is important to review how to operate on the matrices. The most important operation for our purposes is multiplication. If we have two square matrices of the same size:

\(\begin{bmatrix} P_{11} & P_{12} & P_{13} & \dots & P_{1n} \\ P_{21} & P_{22} & P_{23} & \dots & P_{2n} \\ P_{31} & P_{32} & P_{33} & \dots & P_{3n} \\ \vdots & \vdots & \vdots & \ddots & \vdots\\ P_{n1} & P_{n2} & P_{n3} & \dots & P_{nn} \end{bmatrix}\) \(\begin{bmatrix} Q_{11} & Q_{12} & Q_{13} & \dots & Q_{1n} \\ Q_{21} & Q_{22} & Q_{23} & \dots & Q_{2n} \\ Q_{31} & Q_{32} & Q_{33} & \dots & Q_{3n} \\ \vdots & \vdots & \vdots & \ddots & \vdots\\ Q_{n1} & Q_{n2} & Q_{n3} & \dots & Q_{nn} \end{bmatrix}\)

their product is a matrix:

\(\begin{bmatrix} R_{11} & R_{12} & R_{13} & \dots & R_{1n} \\ R_{21} & R_{22} & R_{23} & \dots & R_{2n} \\ R_{31} & R_{32} & R_{33} & \dots & R_{3n} \\ \vdots & \vdots & \vdots & \ddots & \vdots\\ R_{n1} & R_{n2} & R_{n3} & \dots & R_{nn} \end{bmatrix}\)

where \(R_{ij}=P_{i1} \cdot Q_{1j} + P_{i2} \cdot Q_{2j} + \dots + P_{in} \cdot P_{nj}\). Essentially, to find the entry in the \(i^{th}\) row and \(j^{th}\) column, we multiply the \(i^{th}\) row of the first matrix by the \(j^{th}\) row of the the second matrix.

For practice, try to find the product of the following two matrices.

\(\begin{bmatrix} 2 & 4 & 6 \\ 1 & 3 & 5 \\ 1 & 3 & 6 \\ \end{bmatrix} \begin{bmatrix} 1 & 2 & 3 \\ 3 & 2 & 1 \\ 4 & 3 & 1 \\ \end{bmatrix}\)

The answer is at the end of the article.

Applying Ideas

If we have the information for our Markov Chain contained in a matrix, we can find the probabilities of multiple iterations of the Chain by multiplying the matrix with the probabilities by itself. This makes sense if we examine the mechanism for multiplication. When we find the probability for a certain entry, we multiply the probability of getting from a certain state to an intermediary, to the state we want. So, if we want to find the probability of state 4 of a certain chain on move three, given that we started on state 1, we would need to multiply the matrix by itself twice, and find the entry in the first row, fourth column.

When solving problems using Markov Chains, it is important to identify the information, keeping in mind that some of the entries may be 0 if it is impossible to get from one state to another. Let’s go back to the tennis example. If we label the states from left to right, the matrix would look like:

\(\begin{bmatrix} 1 & 0 & 0 & 0 & 0 \\ \frac{1}{3} & 0 & \frac{2}{3} & 0 & 0 \\ 0 & \frac{1}{3} & 0 & \frac{2}{3} & 0 \\ 0 & 0 & \frac{1}{3} & 0 & \frac{2}{3} \\ 0 & 0 & 0 & 0 & 1 \\ \end{bmatrix}\)

If we cube this matrix, we would get:

\(\begin{bmatrix} 1 & 0 & 0 & 0 & 0 \\ \frac{11}{27} & 0 & \frac{8}{27} & 0 & \frac{8}{27} \\ \frac{1}{9} & \frac{4}{27} & 0 & \frac{8}{27} & \frac{4}{9} \\ \frac{1}{27} & 0 & \frac{4}{27} & 0 & \frac{22}{27} \\ 0 & 0 & 0 & 0 & 1 \\ \end{bmatrix}\)

So, if we start at deuce, the probability of winning is \(\frac{4}{9}\).

Final Comments

The matrix representation of Markov Chains is also very useful in computer science. Computers are very well prepared in dealing with matrices, and can multiply them without difficulty. It is much more difficult to try to program a more complex probabilistic system. Markov Chains have been utilized in many wide ranging ways, from financial modeling to particle motion.

Practice Problems

Problem 1. Suppose that we have the following weather observations: If it is sunny today, it will be sunny tomorrow with probability \(\frac{3}{4}\) and cloudy tomorrow with probability \(\frac{1}{4}\). If it is cloudy today, it will be sunny tomorrow with probability \(\frac{2}{5}\), cloudy tomorrow with probability \(\frac{2}{5}\), and rainy tomorrow with probability \(\frac{1}{5}\). If it is rainy today, it will be cloudy tomorrow with probability \(\frac{1}{3}\) and rainy tomorrow with probability \(\frac{2}{3}\). What is the probability it will be rainy 2 days from now if it is sunny today?

Problem 2.(AIME) A bug starts at a vertex of an equilateral triangle. On each move, it randomly selects one of the two vertices where it is not currently located, and crawls along a side of the triangle to that vertex. Find the probability that the bug moves to its starting vertex on its tenth move.

Answers: Matrix answer: \(\begin{bmatrix} 38 & 30 & 16 \\ 30 & 23 & 11 \\ 34 & 26 & 12 \\ \end{bmatrix}\)

We can make a matrix to represent the probabilities of the weather events, where state 1 is sunny, state 2 is cloudy, and state 3 is rainy. The matrix would look like this:

\(\begin{bmatrix} \frac{3}{4} & \frac{1}{4} & 0 \\ \frac{2}{5} & \frac{2}{5} & \frac{1}{5} \\ 0 & \frac{1}{3} & \frac{2}{3} \\ \end{bmatrix}\)

After multiplying this matrix by itself twice, we get that the first entry of the first row is \(\boxed{\frac{53}{80}}\).

(Solution courtesy of AOPS) We can write the probabilities as an exponentiation of the matrix

\(\begin{bmatrix} 0 & .5 & .5 \\ .5 & 0 & .5 \\ .5 & .5 & 0 \\ \end{bmatrix}\)

We can factor out the .5 to get \(\frac{1}{2} \begin{bmatrix} 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \\ \end{bmatrix}\). So raising this all to the tenth power, after some meticulous arithmetic, we get that the upper left entry in the matrix is \(\frac{342}{2^{10}}=\boxed{\frac{171}{512}}\)