Markov chains

Tomorrow’s weather depends only on today’s. Watch a token hop through 3000 days, and the share of days of each kind settle.

Long-run shares

Before the clip you guessed. The start does not matter: from a rainy day or a sunny one, the walk ends up spending about 45 % of its days sunny, 35 % cloudy and 20 % rainy. Choose a different start after the clip and watch the bars go to the same places: from a sunny start the clip’s 3000 days came out 0.437, 0.352 and 0.211, and from a rainy start 0.437, 0.352 and 0.212.

The walk forgets because of how it is built. Each day it hops to tomorrow’s state with chances that depend on today’s state alone, not on any earlier day. A sequence of random states with that property is a Markov chain. I write $X_k$ for the state on day $k$.

Notice that “settled” does not mean the token stops. It keeps hopping every day. What settles is the share of time it spends in each state.

The table of hops

The chances of each hop fit in one table, the transition matrix:

Rows and columns are in the order sunny, cloudy, rainy. Column $q$ lists where a day of type $q$ goes next, so each column adds up to 1. The entry $m_{pq}$ is the chance of going from state $q$ to state $p$:

After a sunny day: sunny again with chance 0.8, cloudy 0.1, rainy 0.1. Many probability books write the same table turned on its side, with rows adding to 1; this site uses columns, as the linear algebra course does.

Each column is one level of a probability tree from Conditional probability. The chance of rain two days after a sunny day adds the three paths through tomorrow:

Many steps: matrix powers

Keep the chances of each state on day $k$ in a vector $\mathbf{u}_k$. Adding over the paths, as above, is exactly multiplying by the matrix:

Start on a sunny day, $\mathbf{u}_0=(1,0,0)$:

By day 10 the chances are within 0.005 of $(0.45,0.35,0.20)$.

The steady state

The shares the walk settles on are a vector $\mathbf{s}$ that one more day does not change:

Solve it from the rainy row: $0.1s_1+0.1s_2+0.6s_3=s_3$ gives $s_1+s_2=4s_3$, and with the three adding to 1, $s_3=0.2$. The sunny row, $0.8s_1+0.2s_2+0.1s_3=s_1$, gives $s_1-s_2=0.1$, so $s_1=0.45$ and $s_2=0.35$. This is the steady state, $\mathbf{s}=(0.45,0.35,0.20)$. These long-run shares are also called the chain’s stationary distribution.

In the language of linear algebra, $\mathbf{s}$ is an eigenvector of $\mathbf{M}$ for the eigenvalue 1. The matrix’s other eigenvalues, 0.6 and 0.5, set how fast the start is forgotten: the gap from the steady state shrinks by a factor of about 0.6 a day, so after 10 days it is about $0.6^{10}=0.006$ of what it was.

The steady state also says how often the walk comes back. If 20 % of days are rainy, rainy days come on average every $1/0.2=5$ days. For a chain like this one, where every state can be reached from every other, the mean time between visits to state $p$ is $1/s_p$: $2.22$ days for sunny, $2.86$ for cloudy, 5 for rainy.

A chain does not always settle. The table $\begin{bmatrix}0&1\\1&0\end{bmatrix}$ swaps two states every day. It has a steady state, $(\tfrac12,\tfrac12)$, but a walk started in one state alternates for ever and its chances never approach it.

States you never leave

Some chains have absorbing states: once entered, never left. A gambler with 2 coins bets 1 coin at a time on a fair flip, and stops on reaching 4 coins or 0. The states are 0 to 4 coins; 0 and 4 absorb.

From 2 coins, reaching 4 has chance $0.5$, by symmetry. From 1 coin it is $0.25$, and from 3 it is $0.75$. In a fair game, the chance of reaching the goal is the fraction of the way there you start.

How many bets does the game last? Let $\mathbf{Q}$ be the hops among the states that do not absorb, 1, 2 and 3. The matrix $(\mathbf{I}-\mathbf{Q})^{-1}$ counts the expected visits to each state before the game ends:

Each column belongs to one starting state, and its sum is the expected number of bets: 3 from 1 coin, 4 from 2 coins, 3 from 3 coins.

With a coin that the gambler wins only 40 % of the time, the chance of reaching 4 from 2 coins falls to $0.3077$; from 1 coin it is $0.1231$, and from 3 coins $0.5846$. A small edge against you adds up over many bets.

Worked example

1. The weather from a sunny start. $\mathbf{u}_1=(0.8,0.1,0.1)$, $\mathbf{u}_2=(0.67,0.18,0.15)$, $\mathbf{u}_3=(0.587,0.238,0.175)$, and by day 10 $(0.4543,0.3459,0.1998)$. The steady state $(0.45,0.35,0.20)$ is $(9,7,4)/20$. Sunny days return every $2.22$ days on average, cloudy every $2.86$, rainy every 5.

2. The fair gambler. From 2 coins: reaches 4 with chance $0.5$ after 4 bets on average. From 3 coins: chance $0.75$, 3 bets on average.

3. The unfair gambler. With a 40 % coin, from 2 coins: reaches 4 with chance $0.3077$.

Try it yourself. Which add up to 1 in this site’s tables, rows or columns? Columns. In the long run, how many days pass between rainy days on average? Five.

Where you’ll meet this

Weather and queues. Simple weather generators and models of queues, where the state is the number of people waiting, are Markov chains.

Text and speech. Predicting the next word from the last few is a Markov chain over words. Speech recognisers used hidden Markov models for decades: a chain of sounds that is seen only through noisy measurements.

Ranking web pages. A random surfer clicking links is a Markov chain over pages, and the steady state ranks the pages: a page visited often in the long run is important.

Simulation. Many computer methods draw samples from a complicated distribution by running a Markov chain whose steady state is that distribution.

Reference card