Index Ai Academy
Phase 2 · Probability for models

Markov chains

States, a table of what comes next, the chance of a path, and where a chain settles.

About 38 minutes · A free account opens the whole lesson.
Already have an account? Sign in to open this lesson

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
Quick check
A guess before you start. If today is sunny, tomorrow is sunny with chance 0.8. If today is rainy, tomorrow is sunny with chance 0.4. Today is sunny. What is the chance that the day after tomorrow is sunny?
  1. 0.32
  2. 0.72
  3. 0.64
  4. 0.80
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:

TodaySunny tomorrowRainy tomorrow
sunny0.80.2
rainy0.40.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:

P(Xt+1=j∣Xt=i)P(X_{t+1} = j \mid X_t = i)

In plain words: XtX_t is the state at step tt, today, and Xt+1X_{t+1} is the state one step later. The whole expression is the chance of being in state jj tomorrow, given that you are in state ii today.

Something must happen tomorrow, so the chances in each row add up to 1. The columns don't have to.

Quick check
A shop models its customers as active, lapsed or gone. Which row can't belong to a transition table?
  1. gone → active 0.0, lapsed 0.0, gone 1.0
  2. lapsed → active 0.3, lapsed 0.4, gone 0.3
  3. active → active 0.7, lapsed 0.2, gone 0.2
  4. active → active 0.7, lapsed 0.2, gone 0.1
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"])
It runs right here in your browser, with nothing to install.

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.

Quick check
Using the weather table: today is rainy. What does this print?
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))
  1. 0.6 rainy
  2. 0.4 sunny
  3. 0.2 rainy
  4. 0.6 sunny
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.

P(path)=P(s1∣s0)×P(s2∣s1)×…P(\text{path}) = P(s_1 \mid s_0) \times P(s_2 \mid s_1) \times \dots

In plain words: go along the path one move at a time. Look up each move in the table and multiply the numbers together. s0s_0 is the state you start in, and s1s_1, s2s_2 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.

Quick check
Three days: rainy, then sunny, then sunny. Given the first day is rainy, what does this print?
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))
  1. 1.2
  2. 0.32
  3. 0.64
  4. 0.48
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.

Quick check
From the conditional probability lesson: the chance that A happens and then B happens is which of these?
  1. P(A) × P(B), whatever A was
  2. P(B given A) alone
  3. P(A) + P(B given A)
  4. P(A) × P(B given A)
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 PP, 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:

πt+1=πtP\pi_{t+1} = \pi_t P

In plain words: πt\pi_t (pi) is the row of chances for each state at step tt. Multiplying it by the table PP 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 PP describes leaving one state.

Try it now

Then set the vector to 0.5, 0.5 (a coin flip about today): the first answer becomes 0.6.

Quick check
Today is certainly rainy. What does this print?
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))
  1. [0.56 0.44]
  2. [0.16 0.36]
  3. [0.72 0.28]
  4. [0.4 0.6]
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.

In your own words
In your own words: why do you add the routes when you look two days ahead, but multiply along each route?

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.

Drill

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"]))
In the lesson, your code is checked as you write it.
Drill

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 the lesson, your code is checked as you write it.

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.

In your own words
What does multiplying a distribution by the transition matrix do, in plain words?

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.

Quick check
A bigram model has read "the bank of the" and must choose the next word. What does it base the choice on?
  1. Only the last word, "the"
  2. The two words "of the" together
  3. The first word of the sentence
  4. All four words, weighted equally
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

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())))
In the lesson you can change this and run it.

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.

Quick check
What does this print? A bigram table is built from counts, and each row is turned into chances.
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())
  1. [[0.5, 0.17], [0.08, 0.25]]
  2. [[0.75, 0.25], [0.25, 0.75]]
  3. [[0.6, 0.2], [0.1, 0.3]]
  4. [[6.0, 2.0], [1.0, 3.0]]
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.

Quick check
A model's code draws the next word with rng.choice(words, p=row) and stops with 'probabilities do not sum to 1'. What is the likely cause?
  1. The Markov property is false
  2. The vocabulary is too large for a single table
  3. The row holds counts, never divided by the row's total
  4. The seed is wrong
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.

In your own words
What is a stationary distribution, and what does it tell you about a chain?

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?

  1. The chances for the next state depend only on the current state
  2. Every state is equally likely at every step
  3. The process must return to the state it started in
  4. The chances for the next state depend on the whole history

Answer it at the end of the lesson to see if you're right, and why.

Before this lesson

Used later in

The lessons that list this one as a prerequisite, from the course map.

Keep learning

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
  1. Reading a paper's equations, with shapes FreeΣ, subscripts, hats and bars, translated into Python you can run and test.35 min
  2. Floating point and log spaceGrowth, decay, and why logs turn products into sums.35 min
  3. Shapes at transformer scaleArrays with more axes: batches, sequences, heads.36 min
  4. The linear layer as algebraMany dot products at once: what a neural network layer computes.40 min
  5. Solving and least squaresThe matrix operations you'll see in every formula.36 min
  6. Projections, orthogonality and rank-1 updatesA matrix stretches, rotates and projects space.34 min
  7. Eigenvalues of symmetric matricesThe directions a transformation leaves pointing the same way.36 min
  8. SVD at workCompress data to its most important directions.40 min
  9. Strange geometry in high dimensionsNear-perpendicular random directions, bunched-up distances, and the curse of dimensionality.38 min
  10. Derivatives of the functions models usePower, sum and product rules, so you rarely compute from scratch.35 min
  11. The chain rule with vectorsDerivatives of functions inside functions: the heart of backprop.40 min
  12. 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
  13. Gradients in matrix form, and how to check themThe vector of all partial derivatives: which way is uphill.35 min
  14. Why training is fast or slowSecond derivatives, minimum or maximum, why curvature caps the learning rate, convex losses and Newton's method.40 min
  15. The chain rule of probabilityUpdate beliefs when new evidence arrives.40 min
  16. Distributions as objectsRandom variables and the shapes their outcomes take.35 min
  17. Expectation and variance of estimatorsExpected value, variance and standard deviation.35 min
  18. Gaussians at workThe bell curve, and why it shows up everywhere.35 min
  19. Covariance matrices and the multivariate normalCovariance and correlation, curves, outliers and common causes, rank correlation, skew and kurtosis.40 min
  20. Losses are negative log-likelihoodsChoose the parameters that make the data most probable.35 min
  21. Samples and confidence: error bars for an evalEstimate from a sample and say how sure you are.40 min
  22. Priors, MAP and regularizationPriors as pseudo-counts, Beta posteriors, shrinkage for small samples, and which of two rates is really higher.40 min
  23. Markov chainsStates, a table of what comes next, the chance of a path, and where a chain settles.38 min
  24. Softmax at working depthTurn any list of scores into probabilities.35 min
  25. Cross-entropy from logitsThe loss function language models are trained on.40 min
  26. 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
  27. A/B tests and significance, for prompts and modelsTell a real lift from noise.40 min
  28. Comparing two models on the same testPaired results, disagreements, a quick z and a bootstrap for the gap between two models.35 min
  29. Ranking from head-to-head resultsElo updates, Bradley-Terry strengths, and how model leaderboards turn votes into ratings.37 min
  30. 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