Markov chains

What is a Markov chain?

A Markov chain is a simple way to describe something that hops between a few states, one step at a time. The rule that makes it a Markov chain is short: where it goes next depends only on the state it is in right now, not on the whole story of how it arrived.

Weather is the classic picture. Suppose each day is either sunny or rainy. If today is sunny, there is some chance tomorrow is sunny again and some chance it turns rainy. If today is rainy, there is a different pair of chances. The chain does not care what the weather was last week. It looks only at today and rolls the dice for tomorrow.

Here is the surprising part. Run this for a long time and count the fraction of days that came up sunny. That fraction settles down to a fixed number. Start from a sunny day or a rainy one, it makes no difference in the long run. The chain forgets where it began and drifts toward the same steady mix. That settled mix is what most people actually want to know.

How do Markov chains work?

Let us make the pieces precise. A Markov chain has a set of states and a set of transition probabilities. For the weather, take three states: sunny, cloudy and rainy. From each state there is a probability of moving to each state next step, and because the chain has to go somewhere, those probabilities add up to 1.

Collect them in a transition matrix \(P\). The entry \(P_{ij}\) is the probability of going from state \(i\) to state \(j\) in one step. Each row is the full set of options out of one state, so every row sums to 1. A matrix like that is called stochastic.

Now suppose you are not sure what today's weather is, so you describe it as a row vector of probabilities, say \(\pi_0 = (0.5,\ 0.3,\ 0.2)\). Where will you be tomorrow? You multiply: \(\pi_1 = \pi_0 P\). The day after is \(\pi_2 = \pi_1 P = \pi_0 P^2\). In general the distribution after \(n\) steps is the starting vector times the matrix raised to the \(n\)th power:

\[ \pi_n = \pi_0\, P^{\,n}. \]

Push \(n\) up and something clean happens. For a well-behaved chain, \(\pi_n\) stops changing. It reaches a distribution \(\pi\) that stays put when you multiply by \(P\) again:

\[ \pi P = \pi. \]

This \(\pi\) is the stationary distribution. Read it as the long-run fraction of time the chain spends in each state. It is the fixed number the sunny days were creeping toward at Level 1.

Two conditions make the chain settle to a single such \(\pi\) regardless of the start. The chain must be irreducible, meaning you can eventually get from any state to any other, so it does not split into separate worlds. And it must be aperiodic, meaning it does not fall into a rigid cycle that returns to a state only on fixed beats. Weather with a bit of randomness in it satisfies both.

This machinery is everywhere once you look. Google's original PageRank treats a web surfer as a Markov chain, clicking random links, and ranks pages by the stationary probability of landing on them. Predictive text and old-school text generators chain words by what tends to follow the current one. Queues at a checkout, the board in Snakes and Ladders, ion channels flicking open and shut: all are states with memoryless hops between them.

The Markov property and stationary distributions

The Markov property

A discrete-time chain on a countable state space is a sequence of random variables \(X_0, X_1, X_2, \dots\) satisfying \[ P(X_{n+1}=j \mid X_n=i, X_{n-1}=i_{n-1}, \dots, X_0=i_0) = P(X_{n+1}=j \mid X_n=i). \] The entire past is irrelevant once the present is known. When these one-step probabilities do not depend on \(n\), the chain is time-homogeneous and is captured by a single stochastic matrix \(P\) with \(P_{ij} \ge 0\) and \(\sum_j P_{ij} = 1\).

Classifying states

A state is recurrent if the chain returns to it with probability 1, and transient if there is a positive chance it leaves and never comes back. The period of a state is the greatest common divisor of the step counts at which return is possible; a state with period 1 is aperiodic. States that communicate (each reachable from the other) share these traits, so for an irreducible chain the whole chain is recurrent or transient, and has a single period.

Perron and Frobenius

For a finite, irreducible, aperiodic chain the Perron–Frobenius theorem does the heavy lifting. The matrix \(P\) has 1 as a simple eigenvalue, every other eigenvalue has modulus strictly less than 1, and there is a unique left eigenvector \(\pi\) with \(\pi P = \pi\), \(\pi_i > 0\) and \(\sum_i \pi_i = 1\). Because the subdominant eigenvalues shrink under powers, \(P^n\) converges to a rank-one matrix whose every row is \(\pi\): \[ \lim_{n\to\infty} (P^{\,n})_{ij} = \pi_j \quad \text{for every } i. \] Every starting distribution is washed toward the same \(\pi\), and the gap decays geometrically at a rate set by the second-largest eigenvalue modulus. This is exactly the convergence you watch the bars perform.

Beyond the finite discrete case

In continuous time the chain waits an exponentially distributed spell in each state, then jumps; the dynamics are governed by a generator matrix \(Q\) and the distribution evolves as \(\pi(t) = \pi(0)\, e^{Qt}\), with the stationary condition becoming \(\pi Q = 0\). And when the goal is reversed, when you know the distribution \(\pi\) you want and need samples from it, Markov Chain Monte Carlo builds a chain engineered to have \(\pi\) as its stationary distribution, often by imposing detailed balance \(\pi_i P_{ij} = \pi_j P_{ji}\). Methods like Metropolis–Hastings and Gibbs sampling then just run the chain and collect states, turning the convergence theorem into a practical way to sample distributions no one can write down in closed form.