Every step a reinforcement learning agent takes — every word an LLM picks — every denoising step in Stable Diffusion — is one transition in a Markov chain. One core idea ("the future only depends on the present") links PageRank, RLHF, diffusion models, and AlphaGo. Learn this one math object, get four ML breakthroughs for free.
Learning Objectives
After this lesson, you will be able to:
Understand the Markov property -- the future depends only on the present, not the path you took to get there -- and recognise where it shows up in modern AI
Compute transition matrices, k-step transitions, and stationary distributions, and see why solving for the stationary distribution is just an eigenvector problem from a previous lesson
Extend Markov chains to MDPs (states + actions + rewards + discount), and write down the Bellman equations that every value-based reinforcement learning algorithm minimises
Connect Markov chains to PageRank, MCMC, diffusion-model forward processes, and autoregressive LLM decoding, and explain why the same equation underlies all of them
Build this --> Build a "PageRank from Scratch" tool that takes a tiny website (5-10 pages with links between them), constructs the transition matrix, and finds the stationary distribution two ways -- iterating π_{t+1} = π_t P until it stops changing, and computing the dominant eigenvector directly. Watch them give the same answer
This is the equation that runs reinforcement learning. The Markov property looks deceptively simple, but stacking it on top of itself produces some of the deepest equations in modern AI: the Bellman equation, the diffusion forward process, the autoregressive decoding loop in every LLM. Get this lesson and you can read RL, diffusion, and decoding papers without flinching.
A Markov chain is a sequence of random variables X_0, X_1, X_2, … where each X_{t+1} depends only on X_t, not on the full history. Formally:
P(Xt+1=x′∣Xt=x,Xt−1,…,X0)=P(Xt+1=x′∣Xt=x)
Try it! Open the Python REPL (bottom-right of the screen: click Quick Actions, then Python) and type these lines yourself.
This is not always literally true of the real world. Yesterday's weather genuinely tells you something about tomorrow's beyond just today's. But if we enrich the state to include yesterday's weather as well, the Markov property snaps back into place. So in practice, the Markov property is not a limit on what you can model -- it is a discipline on what you put in your state.
What Do You Think?
A chess engine is deciding its next move from the current board position. Does the engine need to know the full move history to play optimally, or is the position alone enough?
Suppose tomorrow's weather depends only on today's, with these transition probabilities:
If today is sunny, tomorrow is sunny with probability 0.8 and rainy with probability 0.2
If today is rainy, tomorrow is sunny with probability 0.4 and rainy with probability 0.6
We arrange these into a transition matrixP, where P_ij = "probability of going from state i to state j":
P=[0.80.40.20.6]
If the state distribution today is π_0 = [1, 0] (definitely sunny), tomorrow's distribution is:
π1=π0P=[10][0.80.40.20.6]=[0.80.2]
Note on convention. This lesson uses row vectors (π_{t+1} = π_t P) because that is what most RL textbooks use. Some linear-algebra textbooks (and PyTorch code that prefers column vectors) write the same thing as π_{t+1}^T = P^T π_t^T. They are mathematically identical -- just different sides of the same product.
Play with a live 3-state chain below. Edit the transition matrix P, watch the state distribution π_t evolve one step at a time, and see how the particles redistribute. Try the "Sticky", "Mixing" and "Absorbing" presets to feel how the dynamics change.
What is the probability of being sunny two days from now, given today is sunny? You can either branch out by hand:
Sunny → Sunny → Sunny: 0.8 × 0.8 = 0.64
Sunny → Rainy → Sunny: 0.2 × 0.4 = 0.08
Total: 0.72
…or you can just compute P^2. The two-step transition matrix is P raised to the second power.
Pijk=P(Xt+k=j∣Xt=i)
For our weather chain, P^2 = [[0.72, 0.28], [0.56, 0.44]]. So sunny → sunny in two steps has probability 0.72, matching our hand calculation. As k grows, something interesting happens to P^k: the rows start to look identical. Try it for k = 50:
A stationary distributionπ is a state distribution that is invariant under one step of the chain:
π=πP
Stop and notice: π = π P says that π is a left eigenvector of P with eigenvalue 1. Solving for the stationary distribution is the same eigenvector problem you saw in lesson 4 -- there is no new linear algebra here, only a new application.
For the weather chain, working it out:
π = π P gives π_S = 0.8 π_S + 0.4 π_R and π_R = 0.2 π_S + 0.6 π_R
Both reduce to π_S = 2 π_R
Combined with the normalisation π_S + π_R = 1, we get π_S = 2/3, π_R = 1/3
Over the long run, two-thirds of days are sunny, one-third rainy -- regardless of where the chain started. That is the stationary distribution at work.
Re-open the simulator and try the "Cycle" preset (forces A → B → C → A). Notice how π_toscillates instead of settling -- the cyclic structure prevents convergence even though every state is visited equally often on average. Now try the "Random walk" preset and watch the same machinery quickly produce a uniform stationary distribution.
Loading visualization...
Time to verify everything you just saw. The playground below computes P^t for several t and watches the rows align, then solves for the stationary distribution directly via eigendecomposition -- the two answers must agree.
A few mild conditions guarantee that the stationary distribution is unique and that π_t → π from any starting state:
Irreducibility: every state can reach every other state in finite time. There are no isolated islands.
Aperiodicity: there is no fixed cycle length you are forced into. (Formally: the GCD of return times to any state is 1.)
Markov chains satisfying both conditions are called ergodic. For an ergodic chain, the stationary distribution is unique, and it is the limit of π_t from any starting distribution. You do not need to memorise these conditions in detail -- the takeaway is that "well-behaved" chains have a single long-run answer.
If a chain is reducible (multiple disconnected groups of states), each group has its own stationary distribution. If it is periodic (e.g. always alternates A → B → A → B), π_t oscillates instead of converging, even though averages converge.
Quick check
State 3 of a 3-state Markov chain has P[3, 3] = 1 (and the third row is otherwise 0). What kind of state is this?
How fast does π_t converge to π? The answer is governed by the second-largest eigenvalue of P (in absolute value), often written |λ_2|. The gap 1 − |λ_2| is called the spectral gap, and convergence is exponentially fast at rate |λ_2|^t. A chain with a small spectral gap mixes slowly; a chain with a near-zero λ_2 snaps almost instantly to its stationary distribution. This single number controls how many MCMC samples you need, how quickly PageRank iterations converge, and how diffusion-model schedules trade off forward-process steps for sample quality.
A hidden Markov model (HMM) has a latent Markov chain X_t (the "true" state) and observations Y_t that are generated from X_t via an emission distribution. You see the Y_ts but not the X_ts; algorithms like Viterbi and Baum-Welch reconstruct the most likely hidden sequence or fit the parameters by EM. HMMs were the dominant speech-recognition technology before deep learning, and they remain useful in bioinformatics. Conceptually, attention's autoregressive sampling is a generalisation: at each step, you condition on the full prefix (the "state") and sample the next token (the "observation").
#Markov Decision Processes: Adding Actions and Rewards
So far the chain has just evolved on its own. Markov Decision Processes (MDPs) add the missing ingredient: decisions. At each step, you (the agent) pick an action a, the environment transitions to a new state, and the environment hands you a reward.
An MDP is a tuple (S, A, P, R, γ):
S: state space (where you can be)
A: action space (what you can do)
P(s' | s, a): transition function -- the probability of landing in state s' after taking action a in state s
R(s, a) or R(s, a, s'): reward function -- the immediate reward for the transition
γ ∈ [0, 1]: discount factor -- how much future reward is worth compared to immediate reward
The agent follows a policyπ(a | s), which prescribes the probability of taking action a in state s. This π is not the same as the stationary-distribution π from earlier -- yes, the symbol collides. RL textbooks lean on this overload heavily; just be aware.
The agent's job is to find a policy that maximises the expected discounted return -- the expected sum of discounted future rewards.
Gt=Rt+1+γRt+2+γ2Rt+3+⋯=k=0∑∞γkRt+k+1
Why discount? Three reasons: (1) it keeps the sum finite even on infinite horizons; (2) it matches human / financial impatience; (3) it makes the math nice -- the Bellman operator is a contraction, which we will see in a moment.
The value functions satisfy a beautiful recursive structure. The expected return starting from s equals the expected immediate reward plus the discounted expected return from the next state:
These are the Bellman expectation equations. They are systems of linear equations -- the value functions are uniquely determined by the policy and the MDP.
The really powerful version is the Bellman optimality equation, which describes the value of the best possible policy:
V∗(s)=amaxs′∑P(s′∣s,a)[R(s,a,s′)+γV∗(s′)]
The Bellman optimality is non-linear (because of the max), but it has a unique solution V^* and a corresponding optimal policy π^* that achieves it. The reason it has a unique solution is that the Bellman optimality operator is a contraction.
What Do You Think?
You are designing an MDP for a self-driving car. Episodes are not guaranteed to terminate (the road can be infinitely long). If you set the discount factor γ = 1.0, what is the most likely failure mode?
Two classical algorithms turn the Bellman equations into computational procedures:
Value iteration: start with any V_0. Repeatedly apply V_{k+1}(s) = max_a Σ_{s'} P(s'|s,a)[R + γ V_k(s')]. Converges to V^* geometrically. Extract the optimal policy π^*(s) = argmax_a [...] at the end.
Policy iteration: alternate between (a) policy evaluation -- solve the Bellman expectation equation to get V^π for the current π -- and (b) policy improvement -- update π(s) ← argmax_a Q^π(s, a). Converges in finitely many iterations on finite MDPs.
These are Sutton & Barto Chapter 4 territory, and they are the conceptual backbone of every modern RL method. Q-learning is value iteration with a learned Q_θ. PPO is approximate policy iteration with a stochastic policy and a trust-region constraint. Knowing the Bellman equations means recognising every paper as a variation on this theme.
Put together everything in this lesson and you can read most of modern AI's "stochastic" math in one breath.
F.softmax is what RL uses for π(a | s) in policy-gradient methods -- a Boltzmann policy π(a|s) ∝ exp(Q(s,a) / τ) is just softmax over Q-values.
Autoregressive LLM generation is a Markov chain on tokens, where the state is the full prefix and the action is the next token. Beam search, top-k, top-p (nucleus sampling), and temperature are all decoding policies on this chain. Constrained decoding (forcing JSON output, regex schemas) is constrained MDP territory -- you are clipping the action space to legal next tokens.
DDPM diffusion is the cleanest example of a Markov chain in modern generative AI. The forward process q(x_t | x_{t-1}) = N(x_t; √(1−β_t) x_{t-1}, β_t I) is a Markov chain on latent images. Because of the Markov property and Gaussian conjugacy (multivariate-Gaussian lesson), the marginal q(x_t | x_0) has a closed form -- which is what makes the DDPM training objective a single-step regression and not a 1000-step Monte Carlo estimate.
The mandatory bridges, stated explicitly so you can come back and find them:
PageRank is the stationary distribution of the link Markov chain on the web. Google's original PageRank was an eigenvector computation (lesson 4) on a stochastic transition matrix (this lesson).
Diffusion models' forward process q(x_t | x_{t-1}) = N(x_t; √(1−β_t) x_{t-1}, β_t I) is a Markov chain. The Markov property is what makes the closed-form q(x_t | x_0) derivation possible -- without it, training would be intractable.
Q-learning trains a neural network Q_θ(s, a) to satisfy the Bellman optimality equation: Q_θ(s, a) ← R + γ max_{a'} Q_θ(s', a'). The Bellman optimality from this lesson is the fixed-point that DQN, Rainbow, and all value-based RL methods chase.
PPO and TRPO use trust-region constraints (Lagrangian / KL-bounded updates). The discount factor γ in the Bellman equation reappears in the GAE advantage estimator: Â_t = Σ_l (γλ)^l δ_{t+l} where δ is the TD error.
MCMC samplers (Metropolis-Hastings, Gibbs, Hamiltonian Monte Carlo) construct ergodic Markov chains whose stationary distribution is the target posterior. Bayesian deep learning's posterior sampling, used in tools like PyMC and NumPyro, is built on these Markov-chain foundations.
Here is PageRank from scratch -- the algorithm that built Google -- in about thirty lines. It is just a stationary-distribution computation on the link graph.
What does the Markov property say about a process?
Next up: Optimization & Gradient Descent -- you have already seen it once, and now you can read its Bellman cousins. Then we layer on convex optimisation theory, and finally the stochastic-calculus chapter that makes diffusion models speak the same language as everything you just learned here.