Markov Chains

The game of Monopoly is the worst board game ever. After you go around the board a couple times, everyone knows who's going to win. Then you have a 2.5 hour slow bleed to get to the inevitable finish, punctuated with various fights between family members.

Here's another thing about Monopoly...the probabilities for any individual turn (where your little top hat will end up) depend only on your current location. It doesn't matter where I was last turn; it only matters where I am now. This is the defining characteristic of a technique in probability called Markov Chains.

Applications of Markov Chains go well beyond board games. This is one of the engines that allow us to search the internet! Let's look into it.

Markov Chains

We will start with a few definitions:

Definition: A probability vector is a vector of nonnegative entries that all add up to 1.

Definition: A stochastic matrix is a square matrix whose columns are all probability vectors.

Note

Stochastic just means "random".

Definition: A Markov Chain is a sequence of probability vectors generated by a stochastic matrix $\large P$:

$$\large \begin{split} \vec{x}_1&=P\vec{x}_0 \\ \vec{x}_2&=P\vec{x}_1=P^2\vec{x}_0 \\ \vec{x}_3&=P\vec{x}_2=P^3\vec{x}_0 \\ \vdots &\vdots \quad \vdots\\ \vec{x}_{k+1}&=P\vec{x}_k=P^k\vec{x}_0 \\ \end{split} $$

Note

We see that we are computing $\large P^k$ for large $\large k$. Remember, this is easiest and fastest if we have the diagonalization of $\large P$!

Note

It is a fact that if $\large P$ is a stochastic matrix, and $\large \vec{x}$ is a probability vector, then $\large P\vec{x}$ will also be a probability vector. Essentially, the columns in the stochastic matrix redistribute the values in $\large \vec{x}$, but the total quantity in $\large \vec{x}$ remains 1.

Markov chains are used to model probabilities in dynamic situations where the probability of an event depends only on the current state. Here are two small examples:

Weather Prediction

We will make a simple model. If today is sunny, there's a 90% chance that tomorrow will be sunny (leaving a 10% chance that tomorrow will be rainy). If today is rainy, there's a 50% chance that tomorrow will be rainy too. We can visualize this chain with the following graph:

Our stochastic matrix is:

$$\large P = \begin{bmatrix} 0.9 & 0.5\\ 0.1 & 0.5\\ \end{bmatrix} $$

Note that each column is a probability vector (it adds up to 1).

Language Model

Markov himself chose 20,000 letters from a Russian novel (Alexander Pushkin's Yevgeniy Onegin). He counted how many vowels were followed by a consonant and how many consonants were followed by vowels. He arrived at the following stochastic matrix:

$$\large P = \begin{bmatrix} 0.128 & 0.663\\ 0.872 & 0.337\\ \end{bmatrix} $$

The first column includes the probability that a vowel is followed by another vowel (0.128) or a consonant (0.872). The second gives the probability that a consonant is followed by another consonant (0.663) or by a vowel (0.337).

Steady State (Equilibrium)

Let's use the weather example above and actually build a Markov Chain. Let's start with a 50/50 split:

$$\large \vec{x}_0=\begin{bmatrix} 0.5\\ 0.5\\ \end{bmatrix} $$

If we iterate, we'll get the following chain:

$$\large \begin{split} \vec{x}_1&=\begin{bmatrix} 0.7000\\ 0.3000\\ \end{bmatrix},\quad \vec{x}_2=\begin{bmatrix} 0.7800\\ 0.2200\\ \end{bmatrix}, \quad \vec{x}_3=\begin{bmatrix} 0.8120\\ 0.1880\\ \end{bmatrix},\quad \vec{x}_4=\begin{bmatrix} 0.8248\\ 0.1752\\ \end{bmatrix},\quad \vec{x}_5=\begin{bmatrix} 0.8299\\ 0.1701\\ \end{bmatrix}\\ \vec{x}_{6}&=\begin{bmatrix} 0.8320\\ 0.1680\\ \end{bmatrix},\quad\vec{x}_{7}=\begin{bmatrix} 0.8328\\ 0.1672\\ \end{bmatrix},\quad\vec{x}_{8}=\begin{bmatrix} 0.8331\\ 0.1669\\ \end{bmatrix},\quad\vec{x}_{9}=\begin{bmatrix} 0.8332\\ 0.1668\\ \end{bmatrix},\quad\vec{x}_{10}=\begin{bmatrix} 0.8333\\ 0.1667\\ \end{bmatrix} \end{split} $$

We see that the process is converging to something. There appears to be a limit involved in these iterations. Just to make sure, let's really ramp it up:

$$\large \vec{x}_{100}=P\vec{x}_{99}=\begin{bmatrix} 0.8333\\ 0.1667\\ \end{bmatrix} $$

Definition: This process will often (not always!) have a limit: $\large \displaystyle \lim_{k\to\infty}\vec{x}_k=\vec{q}$. When the limit does exist, we call it a steady state vector or equilibrium vector. The equilibrium vector is characterized by the equation $\large P\vec{q}=\vec{q}$.

Note

The equation for the equilibrium vector is an eigenvector equation with eigenvalue 1. It is a fact that any stochastic matrix has $\large \lambda=1$ as an eigenvalue.

Note

What does it mean for $\large \left<.8333,.1667\right>$ to be an equilibrium vector for our weather model? It means in the long term, 83% of the days will be sunny.

Now that we know the steady state probability vector is an eigenvector with $\large \lambda=1$, we can find it directly. Here's how we do that for the weather model example:

Warning

In the video, we are reminded that our process of finding an eigenvector doesn't naturally generate probability vectors. We normalize the vector to make sure the terms add up to 1.

Finding the Steady State

We've seen that we can find the steady state as the eigenvector of $\large P$. There is another way. Let's go back to the weather model for a moment. Look at the following matrix:

$$\large P^{100}=\begin{bmatrix} 0.8333 & 0.8333\\ 0.1667 & 0.1667\\ \end{bmatrix} $$

We see that if we raise $\large P$ to increasingly large powers, we will arrive at a matrix where every column is the steady state probability vector.

PageRank

Perhaps the most impactful application of Markov Chains in the Google PageRank algorithm. This is the algorithm that decides how to rank the millions of pages that turn up when we put "Linear Algebra" in the search bar. We really wouldn't have a useful internet without it, and we'll see a very simplified version here.

Consider a small internet consisting of 7 pages as shown:

The 7 pages are labeled, and the arrows indicate links between pages. We see, for example, that Page 2 contains links to Page 1 and to Page 5. Page 4 is linked to only by Page 3, and it doesn't have any outgoing links. We can turn this into a stochastic matrix, where $\large P_{i,j}$ represents the fraction of Page i's outgoing links that go to Page j:

$$\large P =\begin{bmatrix} 0 & 1/2 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 1/3 & 0 & 1/2 & 0 & 0\\ 1 & 0 & 0 & 0 & 0 & 1/3 & 0\\ 0 & 0 & 1/3 & 0 & 0 & 0 & 0\\ 0 & 1/2 & 0 & 0 & 0 & 1/3 & 0\\ 0 & 0 & 1/3 & 0 & 1/2 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 1/3 & 0\\ \end{bmatrix} $$

Two problems arise if we try to just use $\large P$:

• The "dead end" pages (Pages 4 and 7 have no outgoing links) are a problem mathematically - these columns are not probability vectors! We replace them with even odds to all pages: a column of all $\large 1/7$ (or $\large 1/n$ if there are $\large n$ web pages).
• It's possible to have little disconnected islands of pages. To fix this, Google defines the "Google Matrix" $\large G$:

$$\large G = cP+(1-c)K$$

where $\large c$ is a number in $\large (0,1)$, and $\large K$ is a matrix full of $\large 1/7$'s.

Note

The Google Matrix is huge, where each column has over a billion entries.

If we choose $\large c=0.85$, we get the following Google Matrix in our example:

$$\large G = \begin{bmatrix} 0.0214 & 0.4464 & 0.0214 & 0.1429 & 0.0214 & 0.0214 & 0.1429 \\ 0.0214 & 0.0214 & 0.3048 & 0.1429 & 0.4464 & 0.0214 & 0.1429 \\ 0.8714 & 0.0214 & 0.0214 & 0.1429 & 0.0214 & 0.3048 & 0.1429 \\ 0.0214 & 0.0214 & 0.3048 & 0.1429 & 0.0214 & 0.0214 & 0.1429 \\ 0.0214 & 0.4464 & 0.0214 & 0.1429 & 0.0214 & 0.3048 & 0.1429 \\ 0.0214 & 0.0214 & 0.3048 & 0.1429 & 0.4464 & 0.0214 & 0.1429 \\ 0.0214 & 0.0214 & 0.0214 & 0.1429 & 0.0214 & 0.3048 & 0.1429 \end{bmatrix} $$

If we raise this to a large power, we get the following, which contains the steady state probability vector in each column:

$$\large G^{100}=\begin{bmatrix} 0.1163 & 0.1163 & 0.1163 & 0.1163 & 0.1163 & 0.1163 & 0.1163 \\ 0.1686 & 0.1686 & 0.1686 & 0.1686 & 0.1686 & 0.1686 & 0.1686 \\ 0.1913 & 0.1913 & 0.1913 & 0.1913 & 0.1913 & 0.1913 & 0.1913 \\ 0.0988 & 0.0988 & 0.0988 & 0.0988 & 0.0988 & 0.0988 & 0.0988 \\ 0.1641 & 0.1641 & 0.1641 & 0.1641 & 0.1641 & 0.1641 & 0.1641 \\ 0.1686 & 0.1686 & 0.1686 & 0.1686 & 0.1686 & 0.1686 & 0.1686 \\ 0.0924 & 0.0924 & 0.0924 & 0.0924 & 0.0924 & 0.0924 & 0.0924 \end{bmatrix} $$

We see that every column is the same, as expected. The steady state vector gives us our ranking. The pages, in order, are: 3, 2 and 6 (tied), 5, 1, 4, 7.

Note

As mentioned, we've outlined the basic idea of PageRank. Google has added much to this since it was invented in 1996. Some of the additions include a way to weigh links differently if they get clicked more often, anti-spam efforts, and the addition of both AI outputs and advertised pages among the displayed results.

Section Outcomes

I can:

• Identify probability vectors and stochastic matrices.
• Generate a Markov chain from a stochastic matrix.
• Find the steady state probability vector for a stochastic matrix (either by finding eigenvectors or by raising $\large P$ to a large power).
• Interpret steady state vectors probabilistically.