Markov Chains

A system that leaps from state to state where the next destination only depends on where you are right now, not how you got there.

Three states linked by transition probabilities whose rows sum to 1 settle to stationary pi equals pi P, with the self-loop holding mass in place

Why Does This Exist?

Search rankings, queueing, genetics, reinforcement learning, and text generation all ask the same question: if a system hops between states with fixed odds, where does it end up after many hops? You cannot answer by listing paths, because the path count explodes. You need an object that steps a whole distribution forward at once.

That object is the transition matrix, and the chain is the process it drives. Without it you simulate one walk at a time and hope. With it you compute where the mass goes, which states trap it, and whether a long-run balance exists at all.

This page teaches the chain and its balance. The sampling method built on top is Markov chain Monte Carlo. The continuous-time cousin with random arrival times is Poisson processes. The belief-update setting where chains meet data is Bayesian inference.

The one idea you need first

A distribution over states is a list of probabilities that sums to 1, such as $[0, 0.6, 0.4]$ meaning 0 percent chance at $A$ , 60 at $B$ , 40 at $C$ . A matrix product of a row distribution by a square matrix returns another row distribution. Chains are repeated applications of that step, which is why matrix multiplication is worth a glance first.

Think of It Like This

Three courtyards with signposted exits

A school has three courtyards: $A$ , $B$ , and $C$ . Every bell, each student follows the signs from wherever they stand. From $A$ , six in ten head to $B$ and four in ten to $C$ . From $B$ , four in ten drift back to $A$ while six in ten stay, lounging by the fountain. From $C$ , half go to $A$ and half to $B$ .

No one remembers yesterday. Your next courtyard depends only on the one you are in now. That forgetfulness is the Markov property, and it is what makes the maths tractable.

After many bells the crowds settle into a pattern that reproduces itself: the flows out of each courtyard exactly balance the flows in. Students still move every bell, but the headcounts stop changing. That balance is stationarity.

Where it stops: real students get bored and break routine. This model never does. Fixed odds forever is the assumption, and a changed sign breaks the prediction.

How It Actually Works

Label the states $A$ , $B$ , $C$ . The transition matrix $P$ collects one-step odds, with $P_{ij}$ meaning the chance of moving from $i$ to $j$ . In plain words: each row is a full set of exit odds from one state, so each row sums to 1.

The diagram uses:

P = \begin{bmatrix} 0 & 0.6 & 0.4 \\ 0.4 & 0.6 & 0 \\ 0.5 & 0.5 & 0 \end{bmatrix}

Rows are $A$ , $B$ , $C$ in order. Check them: $0 + 0.6 + 0.4 = 1$ , $0.4 + 0.6 + 0 = 1$ , $0.5 + 0.5 + 0 = 1$ . The $0.6$ self-loop at $B$ is the focal loop in the picture. It holds mass in place each step, which slows mixing and raises the long-run share of $B$ .

A distribution $\pi_t$ steps forward by right multiplication:

\pi_{t+1} = \pi_t P

Here $\pi_t$ is the row distribution at time $t$ . Stationarity means the distribution reproduces itself, written $\pi = \pi P$ . That equation is a balance condition: inflows equal outflows at every state.

Worked example

Start everyone at $A$ , so $\pi_0 = [1, 0, 0]$ . One step picks out row $A$ :

\pi_1 = [0, 0.6, 0.4]

Nobody stays at $A$ . Sixty percent sit at $B$ , forty at $C$ .

Step again with $\pi_1$ . Only $B$ and $C$ contribute, weighted 0.6 and 0.4:

\pi_2 = 0.6 \times [0.4, 0.6, 0] + 0.4 \times [0.5, 0.5, 0] = [0.24 + 0.20, 0.36 + 0.20, 0] = [0.44, 0.56, 0]

So after two bells, 44 percent are at $A$ and 56 at $B$ , none at $C$ . $C$ empties because nothing points into it from $B$ and its own residents all left.

Keep stepping and the distribution settles near $\pi \approx [0.294, 0.588, 0.118]$ . You can verify it: $0.4 \times 0.588 + 0.5 \times 0.118 = 0.294$ , and $0.6 \times 0.294 + 0.6 \times 0.588 + 0.5 \times 0.118 = 0.588$ , with the third entry $0.4 \times 0.294 = 0.118$ . Rows sum to 1 and $\pi P = \pi$ holds within rounding.

Code

The point is the check: stepping a distribution by $P$ reproduces the hand numbers, and the stationary guess reproduces itself.

1P = [[0.0, 0.6, 0.4], [0.4, 0.6, 0.0], [0.5, 0.5, 0.0]]2
3
4def step(pi: list[float]) -> list[float]:5    return [pi[0] * P[0][j] + pi[1] * P[1][j] + pi[2] * P[2][j] for j in range(3)]6
7
8print(step([1.0, 0.0, 0.0]))  # -> [0.0, 0.6, 0.4]9print(step([0.0, 0.6, 0.4]))  # -> [0.44, 0.56, 0.0]10print(step([0.2941, 0.5882, 0.1176]))  # -> [0.2941, 0.5882, 0.1176] within rounding

The third line is the stationarity test. If your $P$ rows do not sum to 1, that line drifts and the sums leak away from 1, which is how you catch a typo.

Watch Out For

Reading the matrix in the wrong direction

$P_{ij}$ goes from $i$ to $j$ , rows out and columns in. Transpose it and every flow reverses: your $\pi_1$ from $A$ becomes a column instead of row $A$ , and the numbers stop summing correctly after a few steps.

Fix the convention once. Distributions are rows here and step right ( $\pi P$ ). If a library uses columns ( $P \pi$ ), transpose on import and recheck that each column now sums to 1 before trusting anything.

Assuming a stationary balance always exists and is unique

Some chains never settle. A deterministic flip-flop between two states oscillates forever. A chain with two disconnected islands keeps the starting island's mass forever, so the limit depends on where you began.

Before quoting $\pi$ , check irreducibility (you can reach every state from every state, possibly via others) and aperiodicity (no fixed cycle length). The diagram chain satisfies both, which is why its $\pi$ is meaningful. Without them, long-run averages can mislead.

The Quick Version

A Markov chain moves by fixed odds that depend only on the current state.
The transition matrix $P$ holds those odds with each row summing to 1.
Distributions step by $\pi_{t+1} = \pi_t P$ , so one multiplication moves the whole crowd.
From $[1, 0, 0]$ , this chain gives $[0, 0.6, 0.4]$ then $[0.44, 0.56, 0]$ .
Stationarity $\pi = \pi P$ means inflows balance outflows; here about $[0.294, 0.588, 0.118]$ .
The self-loop at $B$ holds mass and lifts its long-run share.
Rows point out, columns point in. Transposing silently reverses every flow.