Announcements¶

• Homework:
  • Homework 9 out, due Sunday
• Final exam: Monday, May 8 from 12-2pm
• Upcoming office hours:
  • Today: Prof McDonald from 4:30-6pm in CCDS 1341
  • Tomorrow: Peer tutor Rohan Anand from 1:30-3pm in CCDS 16th floor

Lecture 36: Applications of Markov Chains¶

Recap: Eigenvectors¶

Of all of the linear transformations associated with a square matrix, scaling is special because:

If a matrix $A$ scales $x$, then that transformation could also have been expressed without a matrix-vector multiplication, i.e., as $\lambda x$ for some scalar value $\lambda$.

An eigenvector of a matrix $A$ is a special vector that does not change its direction when multiplied by $A$.

The eigenvalues of a matrix $A$ are all of the scalars that an eigenvector can be scaled by.

To find an eigenvalue: we saw that $\lambda$ is an eigenvalue of an $n\times n$ matrix $A$ if and only if the equation

has a nontrivial solution.

Some special cases:

• The eigenvalues of an upper triangular matrix or a lower triangular matrix are the entries on its main diagonal.
• A matrix has an eigenvalue of 0 if and only if it is not invertible (i.e., is singular).

Combining these properties leads to the characteristic equation: a scalar $\lambda$ is an eigenvalue of an $n\times n$ matrix $A$ if and only if $\lambda$ satisfies

This equation yields a polynomial in $\lambda$ of degree $n$, meaning there are at most $n$ solutions.

To find all eigenvectors corresponding to an eigenvalue: compute the null space of the matrix $A-\lambda I.$

(Remember that this forms a subspace, which we call the eigenspace of $A$ corresponding to $\lambda$.)

Recap: Markov chains¶

A difference equation (also known as a dynamical system or recurrence relation) contains two parts:

• we define some vector that describes the state of the system, and
• we formulate a rule that tells us how to compute the next state of the system based on the current state of the system.

A Markov chain is a dynamical system whose state is a probability vector $x_k$ and whose state transitions are determined by a stochastic matrix $P\in R^{n\times n}$, meaning that that

Here:

• A probability vector is a vector of nonnegative entries that sums to 1.
• A stochastic matrix is a square matrix of nonnegative values whose columns each sum to 1.

A important question about a Markov Chain is: what will happen in the distant future?

If $P$ is a stochastic matrix, then a steady-state vector (or equilibrium vector) for $P$ is a probability vector $x$ such that:

We can find a steady state vector by solving the equation $Px=x$, or equivalently

and restricting to vectors $x$ that are probability vectors.

To solve a Markov Chain for its steady state:

• Solve the linear system $(P-I)x=0.$
• The system will have an infinite number of solutions, with one free variable. Obtain a general solution.
• Pick any specific solution (choose any value for the free variable), and normalize it so the entries add up to 1.

36.1 Markov Chains and Eigenvectors¶

We can place the theory of Markov Chains into the broader context of eigenvalues and eigenvectors.

Theorem. The largest eigenvalue of a Markov Chain is 1.

Proof. First of all, 1 is an eigenvalue of a Markov chain and its corresponding vector is the steady state vector $v$. This is because $Av=1\cdot v.$

To prove that 1 is the largest eigenvalue, recall that each column of a Markov Chain sums to 1.

Then, consider the sum of the values in the vector $Ax$.

Let's just sum the first terms in each component of $Ax$:

So we can see that the sum of all terms in $Ax$ is equal to $x_1+x_2+\cdots +x_n$ -- i.e., the sum of all terms in $x$.

So there can be no $\lambda >1$ such that $Ax=\lambda x.$

A complete solution for the evolution of a Markov Chain¶

Previously, we were only able to ask about the "eventual" steady state of a Markov Chain.

But a crucial question is: how long does it take for a particular Markov Chain to reach steady state from some initial starting condition?

Example. Let's use our running example of population movement, defined by $A=\left[\begin{array}{cc}0.95& 0.03\\ 0.05& 0.97\end{array}\right].$

Let's ask how long until it reaches steady state, from the starting point defined as $x_0=\left[\begin{array}{c}0.6\\ 0.4\end{array}\right].$

Remember that $x_0$ is probability vector -- its entries are nonnegative and sum to 1.

The matrix $A$ has the characteristic equation:

Using the quadratic formula, we find the roots of this equation to be 1 and 0.92. (Note that, as expected, 1 is the largest eigenvalue.)

Next, we can find a basis for each eigenspace of $A$ (each nullspace of $A-\lambda I$).

• For $\lambda =1$, a corresponding eigenvector is $v_1=\left[\begin{array}{c}3/8\\ 5/8\end{array}\right].$ This is a steady state vector! (Note that I purposely normalized $v_1$ to be a probability vector.)
• For $\lambda =0.92$, a corresponding eigenvector is $v_2=\left[\begin{array}{c}1\\ -1\end{array}\right].$

Next, we write the initial state $x_0=\left[\begin{array}{c}0.6\\ 0.4\end{array}\right]$ as a linear combination of $v_1$ and $v_2.$ This can be done because $\{v_1,v_2\}$ is obviously a basis for $R^2.$

To write $x_0$ this way, we want to solve the vector equation

In other words:

The matrix $\left[v_1{v}_2\right]$ is invertible, so,

So, now we can put it all together.

We know that

and we know the values of $c_1,c_2$ that make this true.

And then we can use the eigendecomposition to compute subsequent terms $x_k$:

Now note the power of the eigenvalue approach:

And so in general: $$x_k=c_1{v}_1+c_2\left(0.92{)}^k{v}_2\right(k=0,1,2,\dots )$$

And using the $c_1$ and $c_2$ and $v_1,$ $v_2$ we computed above:

This explicit formula for $x_k$ gives the solution of the Markov Chain $x_{k+1}=A{x}_k$ starting from the initial state $x_0$.

In other words: $$x_0=\left[\begin{array}{c}3/8\\ 5/8\end{array}\right]+0.225\left[\begin{array}{c}1\\ -1\end{array}\right]$$
$$x_1=\left[\begin{array}{c}3/8\\ 5/8\end{array}\right]+0.207\left[\begin{array}{c}1\\ -1\end{array}\right]$$
$$x_2=\left[\begin{array}{c}3/8\\ 5/8\end{array}\right]+0.190\left[\begin{array}{c}1\\ -1\end{array}\right]$$
$$x_3=\left[\begin{array}{c}3/8\\ 5/8\end{array}\right]+0.175\left[\begin{array}{c}1\\ -1\end{array}\right]$$
$$...$$
$$x_{\infty }=\left[\begin{array}{c}3/8\\ 5/8\end{array}\right]$$

As $k\to \infty$, $(0.92{)}^k\to 0$. Thus the Markov chain converges to the steady state $x_k\to \left[\begin{array}{c}3/8\\ 5/8\end{array}\right].$

36.2 An early application of Markov Chains¶

Markov Chains have been deployed in many different applications. The earliest domain they were useful in was analysis of written language.

We'll walk through some of the early experiments in this domain.

Our goal: Make our computer write us a sentence.

Version 0¶

Generate text by randomly selecting letters of the alphabet. Letters are equiprobable.

This looks more like a password generator than a text generator.

Fortunately, we know some things about English! Firstly, that not every letter occurs with the same frequency -- 's' and 'e' will be more common than 'q' and 'z'.

Version 1¶

Generate text that reflects the relative frequencies of each letter in English.

This is slightly more comprehensible. But we can do better.

Letter frequency analysis is what Andrey Markov conducted in his initial paper on Markov Chains. He took Alexander Pushkin's Eugene Onegin and sampled, by hand, the first 20,000 letters of the novel.

He counted the number of vowels, the number of consonants, and the number of vowel-vowel, consonant-consonant, and vowel-consonant pairs.

He found that the first 20,000 letters were 8,638 (43%) vowels and 11,362 (57%) consonants.

If each letter were independent, we would expect the chance of two sequential vowels to be $\left(.43\right)\left(.43\right)=0.1849$. This equates to 3,698 vowel-vowel pairs in 20,000 characters.

But Markov observed 1,104 -- nearly 1/3 the expected number!

Thus, we can conclude what we know intuitively -- that there is a dependence relationship between letters.

Thirty years later, another mathematician began investigating this dependence relationship between letters.

Claude Shannon was a mathematician and early computer scientist. He is considered by many to be the father of information theory, and had a significant impact on the direction of modern computing (including that we store information in bits!). During WWII, Shannon worked as a codebreaker, which led to his later work on English text analysis, information entropy, and redundancy.

Shannon observed that "anyone speaking a language possesses, implicitly, an enormous knowledge of the statistics of the language." He devised multiple experiments to demonstrate this.

For example, imagine the following game:

1. Formulate a hidden sentence.
2. Ask the player to guess the next letter.
3. If they are correct, tell them and proceed. If they are incorrect, increment the number of guesses and ask them to guess again.

One observation from this: even beyond the likelihood of moving between consonants and vowels, there are many common combinations of letters. And the preceeding letters tell us a lot about what letter is most likely to come next!

Version 2¶

Let's analyze some real text and find out which combinations of letters are most likely. In other words, let's estimate the probability of each letter transitioning to another.

Let's write a function that takes our training text, the number of letters to "look back," and the number of characters in our new sentence.

At this point, as we are essentially memorizing whole words, it might be more expedient to switch to a word-based model.

Version 3¶

Randomly select words from our corpus.

Version 4¶

Choose the next word based on the preceeding word.

Summary¶

We're getting close to readable text, but you can imagine there is still a long way to go before we reach grammatically correct or sensical text.

Modern text generation has moved to more complex models, but still operates on the same intuition -- based on the surrounding text, make a good prediction for what letter or word should come next.

(If you want to try some of this yourself, and see examples of Markov Chains deployed for amusement in the wild, check out https://github.com/jsvine/markovify).

Markov chains and their variants are still used in many real applications today.

• Text compression
• Hidden Markov Models are used in automatic speech recognition
• Markov Chain Monte Carlo is used in physics and biology
• Markov Decision Processes (MDP) are used in reinforcement learning
• ...