Markov Chain

6 min read#probability

A random process that hops between states where the next state depends only on the current one, forgetting all earlier history.

Contents

Markov Chain

A Markov chain is a random process with no memory. It lives in a set of states and hops between them at each step, but the rule for where it goes next depends only on where it is now — never on the path that brought it there. This memorylessness (the Markov property) is a drastic simplification, and yet it is rich enough to model weather, board games, queues, shuffles, language, and the random web-surfer behind PageRank.

All the dynamics live in one object: the transition matrix P, whose entry P_{ij} is the probability of jumping from state i to state j. Each row lists where you might go from one state and sums to 1 — you must land somewhere.

From a state to a distribution

Instead of tracking a single wandering token, track a probability distribution over the states — a vector \pi saying how much "mass" sits on each. One step of the chain advances it by a Matrix multiply:

\pi_{t+1} = \pi_t \, P .
(1)

Apply P again and again and, for most chains, the distribution stops changing. It reaches a stationary distribution \pi^\star that satisfies

\pi^\star = \pi^\star P .
(2)

Watch the mass converge

Below are a few states joined by weighted arrows (the transition probabilities). Probability mass — drawn as the area of each node — starts piled on one state and then flows along the arrows every step, splitting according to the weights. No matter where it starts, it sloshes around and then freezes into the stationary distribution: the unique mix that flows into itself unchanged. The bars on the right track the same distribution converging.

A 5-state Markov chain converging to its stationary distribution. Node area is the current probability mass; it flows along weighted arrows each step (power iteration) and settles onto the eigenvector with eigenvalue 1. Bars at right show the same distribution. Auto-resets from a fresh random pile.

When does a chain settle?

Not every chain has a single stationary destiny. A chain that can eventually get from any state to any other (irreducible) and does not lock into a rigid cycle (aperiodic) is guaranteed to converge to one unique \pi^\star from any start. Chains with isolated traps or perfect periodicity can fail this — they may oscillate forever or depend on where they began. When the conditions hold, the long-run behavior is beautifully indifferent to initial conditions, the opposite of the Chaos story.

A Markov chain is also just a Dynamical System whose state is a probability vector and whose rule is the matrix P — randomness and linear algebra, fused.

See also