Markov chains
States, a table of what comes next, the chance of a path, and where a chain settles.
What it covers6
Why it matters
A language model answers one question over and over: given what came before, what comes next? The simplest version of that question looks only at where you are now, not at how you got there. A process like that is called a Markov chain. The bigram model in Phase 5 is one, and so are simple models of the weather, of customers who stay or leave, and of a reader clicking from page to page. This lesson gives you the table that defines a chain and the three things you can do with it: walk it, score a path, and see where it ends up.
What you'll be able to do
- Describe a process as a set of states and the chance of each next state, given the current one
- Read and build a transition table, and check that each row adds up to 1
- Simulate a chain, and work out the chance of a whole path by multiplying along it
- Move a distribution forward with a matrix product, and find where it settles: the eigenvector with eigenvalue 1
- Sample a chain with torch.multinomial, as a bigram language model does
Show the answer
0.72
There are two ways to get there. Sunny tomorrow and sunny again: 0.8 × 0.8 = 0.64. Or rainy tomorrow and then sunny: 0.2 × 0.4 = 0.08. Together, 0.72. Counting every route to an outcome is the heart of this lesson.
The math: states, tables and routes
Purpose. Describe a process by a table of next-state chances, and move chances forward by adding up routes.
This builds on the lesson on conditional probability and on the matrix-vector product of A matrix times a vector (Foundation lesson 55).
Picture a board game where your next square depends only on the square you're standing on and a roll of the dice. How you reached that square makes no difference. That one idea defines a Markov chain.
The squares are called states: the situations the process can be in. For a toy model of the weather the states are "sunny" and "rainy". Each day the weather moves to a new state or stays in the same one, and the chances depend only on today:
| Today | Sunny tomorrow | Rainy tomorrow |
|---|---|---|
| sunny | 0.8 | 0.2 |
| rainy | 0.4 | 0.6 |
This is a transition table. Each row is one "given": the row for sunny holds the chances for tomorrow, given that today is sunny. In the notation of the conditional probability lesson:
In plain words: is the state at step , today, and is the state one step later. The whole expression is the chance of being in state tomorrow, given that you are in state today.
Something must happen tomorrow, so the chances in each row add up to 1. The columns don't have to.
Show the answer
active → active 0.7, lapsed 0.2, gone 0.2
Its chances add up to 1.1. A row lists everything that can happen next, so it must add up to exactly 1.
In Python, a dictionary of dictionaries holds the table: the outer key is today's state, the inner one is tomorrow's.
chain = {
"sunny": {"sunny": 0.8, "rainy": 0.2},
"rainy": {"sunny": 0.4, "rainy": 0.6},
}
for today, row in chain.items():
print(today, "->", row, "| adds up to", round(sum(row.values()), 10))
print("rainy today, sunny tomorrow:", chain["rainy"]["sunny"])The promise that only the current state matters is called the Markov property. It's a simplification, and a bold one. Real weather remembers more than one day. The property is what makes the model small enough to write in a table.
chain = {
"sunny": {"sunny": 0.8, "rainy": 0.2},
"rainy": {"sunny": 0.4, "rainy": 0.6},
}
today = "rainy"
print(chain[today]["rainy"], max(chain[today], key=chain[today].get))Show the answer
0.6 rainy
The row for rainy is sunny 0.4, rainy 0.6. The chance of rain again is 0.6, and rainy is the state with the highest chance in that row.
The chance of a path. How likely is one particular walk? The conditional probability lesson gave the rule for a chain of events: multiply the chance of each step, given the one before. In a Markov chain each step's chance is one cell of the table.
In plain words: go along the path one move at a time. Look up each move in the table and multiply the numbers together. is the state you start in, and , are the states after it.
chain = {
"sunny": {"sunny": 0.8, "rainy": 0.2},
"rainy": {"sunny": 0.4, "rainy": 0.6},
}
path = ["sunny", "sunny", "rainy", "rainy"]
p = 1.0
for now, nxt in zip(path, path[1:]):
print(now, "->", nxt, chain[now][nxt])
p = p * chain[now][nxt]
print("chance of the whole path:", round(p, 4))
zip(path, path[1:]) pairs each state with the one after it, so the loop visits every move once.
chain = {
"sunny": {"sunny": 0.8, "rainy": 0.2},
"rainy": {"sunny": 0.4, "rainy": 0.6},
}
path = ["rainy", "sunny", "sunny"]
p = 1.0
for now, nxt in zip(path, path[1:]):
p = p * chain[now][nxt]
print(round(p, 2))Show the answer
0.32
Two moves: rainy to sunny is 0.4, and sunny to sunny is 0.8. Their product is 0.32.
Show the answer
P(A) × P(B given A)
First A has to happen, then B has to follow it: multiply the chance of A by the chance of B given A. A path through a chain repeats this once per move.
Two steps ahead
Now the opening question. Today is sunny: how likely is sun the day after tomorrow? You don't know what tomorrow will be, so add up every route:
- sunny, then sunny: 0.8 × 0.8 = 0.64
- rainy, then sunny: 0.2 × 0.4 = 0.08
That's 0.72 in all. For each possible middle day you multiplied along the route, then you added the routes.
Doing this for every state at once is a job you already have a tool for. Write the table as a matrix , one row per current state. Write what you know about today as a row of chances, a distribution: one number per state, adding up to 1. One step forward is a matrix product:
In plain words: (pi) is the row of chances for each state at step . Multiplying it by the table gives the row of chances one step later. Each new number is a sum over routes: the chance of being in each state now, times the chance of moving from there.
import numpy as np P = np.array([[0.8, 0.2], [0.4, 0.6]]) today = np.array([1.0, 0.0]) # certainly sunny tomorrow = today @ P day_after = tomorrow @ P print("tomorrow: ", tomorrow) print("day after:", day_after)
The second line is the answer by matrix: 0.72 sunny, 0.28 rainy. The distribution goes on the left of the @ because it's a row, and each row of describes leaving one state.
Then set the vector to 0.5, 0.5 (a coin flip about today): the first answer becomes 0.6.
import numpy as np P = np.array([[0.8, 0.2], [0.4, 0.6]]) today = np.array([0.0, 1.0]) print((today @ P @ P).round(2))
Show the answer
[0.56 0.44]
After one step the chances are the rainy row: 0.4 sunny, 0.6 rainy. A second step gives sunny 0.4 × 0.8 + 0.6 × 0.4 = 0.56, and rainy the remaining 0.44.
Write a sentence or two, then compare it with a good answer in the lesson.
In NumPy and PyTorch: walking, stepping and settling
Purpose. Run a chain as code: simulate it, score a path, move a distribution, and find where it settles.
Walking the chain. To simulate a chain, start in a state and let chance pick each next one, using the row for wherever you are. rng.choice draws one item from a list with the chances you give it:
import numpy as np chain = { "sunny": {"sunny": 0.8, "rainy": 0.2}, "rainy": {"sunny": 0.4, "rainy": 0.6}, } states = ["sunny", "rainy"] rng = np.random.default_rng(7) today = "sunny" path = [today] for day in range(12): row = chain[today] today = str(rng.choice(states, p=[row[s] for s in states])) path.append(today) print(" ".join(path))
The same weather tends to come in runs, because each state is more likely to be followed by itself than by the other. Change the seed and you get another walk through the same table.
The chance of a path
Write path_probability(chain, path): the chance of following path move by move, given that you start in its first state. A path of one state has no moves, so its chance is 1. A move that isn't in the table can't happen, so it makes the chance 0.
def path_probability(chain, path): # multiply the chance of each move along the path return 0 weather = { "sunny": {"sunny": 0.8, "rainy": 0.2}, "rainy": {"sunny": 0.4, "rainy": 0.6}, } print(path_probability(weather, ["sunny", "rainy", "sunny"]))
Any number of steps ahead
Write after(dist, P, n): the distribution n steps after dist, for a chain with transition matrix P. Zero steps returns the distribution unchanged. Use a loop and @.
import numpy as np def after(dist, P, n): # move the distribution forward n steps return dist P = np.array([[0.8, 0.2], [0.4, 0.6]]) print(after(np.array([1.0, 0.0]), P, 3))
In PyTorch. A chain is a matrix and a sampler. torch.multinomial(P[state], 1) draws the next state from the row of the current one: the line a bigram language model runs once per word. The page runs a teaching subset of PyTorch, with the same lines as a real install (the random draws differ, so only the rounded share is shown).
import torch P = torch.tensor([[0.8, 0.2], [0.4, 0.6]]) torch.manual_seed(0) state, sunny = 0, 0 for _ in range(5000): state = torch.multinomial(P[state], 1).item() sunny += state == 0 print(round(sunny / 5000, 1)) dist = torch.tensor([1.0, 0.0]) for _ in range(30): dist = dist @ P print(round(dist[0].item(), 4))
The walk spends about 0.7 of its days sunny, and the exact distribution after 30 steps agrees: 0.6667. Simulation and the matrix product are two routes to the same long-run share.
Where the chain settles. Keep stepping forward and something striking happens: the distribution stops changing.
import numpy as np P = np.array([[0.8, 0.2], [0.4, 0.6]]) for start in ([1.0, 0.0], [0.0, 1.0]): dist = np.array(start) for day in range(30): dist = dist @ P print(start, "->", dist.round(4))
Whether it starts sunny or rainy, after a month the chances are the same: about two days in three are sunny. A distribution that a step leaves unchanged is called a stationary distribution. It tells you the share of time the chain spends in each state over a long run.
Go deeper Does every chain settle?
No. A chain that flips with certainty, A to B and B to A, never stops swinging between the two. And a chain with a state it can't leave, like "gone" for a customer, ends up entirely in that state. The weather chain settles to a mix because every state can reach every other and nothing forces a strict rhythm.
It settles geometrically, and why. Two starting points, one destination. The gap to the long-run share shrinks by a fixed factor each day, 0.4 for this chain, which is the second eigenvalue of P. The settled distribution is the row π with π P = π: an eigenvector of Pᵀ with eigenvalue 1. NumPy's general eig finds it (P is not symmetric, so eigh doesn't apply: see the lesson on symmetric matrices).
import numpy as np import matplotlib.pyplot as plt P = np.array([[0.8, 0.2], [0.4, 0.6]]) for start in ([1.0, 0.0], [0.0, 1.0]): d, sunny = np.array(start), [] for day in range(21): sunny.append(d[0]) d = d @ P plt.plot(sunny, marker="o", label="starts sunny" if start[0] else "starts rainy") plt.axhline(2 / 3, linestyle="--") plt.xlabel("day") plt.ylabel("chance of sun") plt.legend() plt.show() values, vectors = np.linalg.eig(P.T) pi = np.real(vectors[:, np.argmin(abs(values - 1))]) pi = pi / pi.sum() print(sorted(values.real.round(3).tolist()), pi.round(4).tolist()) print(np.allclose(pi @ P, pi))
The eigenvalues are 0.4 and 1.0. The eigenvector for 1.0, scaled to add to 1, is (0.6667, 0.3333): the stationary distribution, and pi @ P == pi is True. Both curves close on the dashed line, the gap shrinking by 0.4 each day.
Write a sentence or two, then compare it with a good answer in the lesson.
In training code: from weather to words
Purpose. See that a bigram language model is this table, and the two ways its table goes wrong.
Swap the states for words and the same table becomes a model of language. The state is the current word. The row for a word holds the chance of each word that could follow it. You get the table from a text by counting which word follows which, then dividing each count by its row's total:
text = "the cat sat on the mat the cat ran" words = text.split() counts = {} for now, nxt in zip(words, words[1:]): if now not in counts: counts[now] = {} counts[now][nxt] = counts[now].get(nxt, 0) + 1 row = counts["the"] total = sum(row.values()) print(row) print({word: round(n / total, 2) for word, n in row.items()})
That is a bigram model, which Phase 5 builds on a full text. It also shows the price of the Markov property. After "the", this model knows nothing about what came before "the". A modern language model drops that limit: it conditions each word on everything so far.
Show the answer
Only the last word, "the"
A bigram model is a Markov chain whose state is the current word, so its next step depends on that word alone. It can't tell this "the" from any other.
Worked example: how many customers are left after a year?
A subscription shop sorts its customers into three states each month: active, lapsed (no order this month) and gone (canceled). Gone is a state with no way out. Starting with every customer active, where are they after 12 months?
import numpy as np states = ["active", "lapsed", "gone"] P = np.array([[0.85, 0.10, 0.05], [0.30, 0.50, 0.20], [0.00, 0.00, 1.00]]) print("each row adds up to:", P.sum(axis=1)) dist = np.array([1.0, 0.0, 0.0]) for month in range(1, 13): dist = dist @ P if month in (1, 6, 12): print("month", month, dict(zip(states, dist.round(3).tolist())))
Each printed row is the share of customers in each state at that month, and each still adds up to 1. The share that is gone only ever grows, because nothing leaves that state. Run the loop for more months and it keeps growing toward 1: this chain's long run is "everyone has left", which is why a shop like this has to keep finding new customers. The table's top-left number, 0.85, is the lever. Change it to 0.95 and compare month 12.
import numpy as np counts = np.array([[6.0, 2.0], [1.0, 3.0]]) print((counts / counts.sum(axis=1, keepdims=True)).round(2).tolist())
Show the answer
[[0.75, 0.25], [0.25, 0.75]]
Each row is divided by its own total: 6 / 8 = 0.75 and 2 / 8 = 0.25; 1 / 4 = 0.25 and 3 / 4 = 0.75. Every row then adds to 1.
rng.choice(words, p=row) and stops with 'probabilities do not sum to 1'. What is the likely cause?Show the answer
The row holds counts, never divided by the row's total
A table built by counting holds counts, not chances. Divide each row by its sum so it adds to 1; numpy refuses a row that doesn't.
Write a sentence or two, then compare it with a good answer in the lesson.
Practice what you just read
- 9 code examples you can edit and run
- a practice exercise that checks your code
- a 5-question quiz
- 10 review cards for spaced repetition
Try a quiz question
What makes a process a Markov chain?
Before this lesson
- The chain rule of probability
- Distributions as objects
- The linear layer as algebra
- Eigenvalues of symmetric matrices
Used later in
Where this lesson leads.
575 lessons in thirteen phases. 176 are free without an account, and a free account opens the rest. See every lesson.
Phase 2 · about 23 hours of study
Math for ML engineers
The Foundation's formulas at working depth: batches, shapes, autograd, stable arithmetic and error bars
30 lessons 1 free
- Reading a paper's equations, with shapes FreeΣ, subscripts, hats and bars, translated into Python you can run and test.35 min
- Floating point and log spaceGrowth, decay, and why logs turn products into sums.35 min
- Shapes at transformer scaleArrays with more axes: batches, sequences, heads.36 min
- The linear layer as algebraMany dot products at once: what a neural network layer computes.40 min
- Solving and least squaresThe matrix operations you'll see in every formula.36 min
- Projections, orthogonality and rank-1 updatesA matrix stretches, rotates and projects space.34 min
- Eigenvalues of symmetric matricesThe directions a transformation leaves pointing the same way.36 min
- SVD at workCompress data to its most important directions.40 min
- Strange geometry in high dimensionsNear-perpendicular random directions, bunched-up distances, and the curse of dimensionality.38 min
- Derivatives of the functions models usePower, sum and product rules, so you rarely compute from scratch.35 min
- The chain rule with vectorsDerivatives of functions inside functions: the heart of backprop.40 min
- Backprop through a linear layer: gradients with shapesThe slope of the loss through Y = XW + b: dX, dW and db derived from one entry, found again from shapes, and checked against autograd.40 min
- Gradients in matrix form, and how to check themThe vector of all partial derivatives: which way is uphill.35 min
- Why training is fast or slowSecond derivatives, minimum or maximum, why curvature caps the learning rate, convex losses and Newton's method.40 min
- The chain rule of probabilityUpdate beliefs when new evidence arrives.40 min
- Distributions as objectsRandom variables and the shapes their outcomes take.35 min
- Expectation and variance of estimatorsExpected value, variance and standard deviation.35 min
- Gaussians at workThe bell curve, and why it shows up everywhere.35 min
- Covariance matrices and the multivariate normalCovariance and correlation, curves, outliers and common causes, rank correlation, skew and kurtosis.40 min
- Losses are negative log-likelihoodsChoose the parameters that make the data most probable.35 min
- Samples and confidence: error bars for an evalEstimate from a sample and say how sure you are.40 min
- Priors, MAP and regularizationPriors as pseudo-counts, Beta posteriors, shrinkage for small samples, and which of two rates is really higher.40 min
- Markov chainsStates, a table of what comes next, the chance of a path, and where a chain settles.38 min
- Softmax at working depthTurn any list of scores into probabilities.35 min
- Cross-entropy from logitsThe loss function language models are trained on.40 min
- KL divergence at workForward against reverse KL, KL between normals, F.kl_div's argument order, a distillation loss with temperature, and a KL penalty against a base model.36 min
- A/B tests and significance, for prompts and modelsTell a real lift from noise.40 min
- Comparing two models on the same testPaired results, disagreements, a quick z and a bootstrap for the gap between two models.35 min
- Ranking from head-to-head resultsElo updates, Bradley-Terry strengths, and how model leaderboards turn votes into ratings.37 min
- Capstone: one problem through five tracksA three-class softmax classifier written from its formula: notation to NumPy, matrix products, cross-entropy, the gradient, and an honest report.45 min
Never trained an AI? Teach a small one to write, right in your browser. It takes about 20 seconds and needs no account. Teach it to write