A fair random walk never drifts, yet its typical distance grows as √n. Markov chains forget their history but keep a stationary distribution. Add a gradient and the same recipe becomes SGD and diffusion models.
A Markov process is random but structured: the next state depends only on the current one. That single rule compresses a whole history into one snapshot and the whole dynamics into a transition table P, where P[i][j] is the chance of i → j and every row sums to 1.
πP = π · 1 − |λ₂| sets the mixing speedSum n independent ±1 steps and the mean stays 0 while the standard deviation grows as √n: about 10 after 100 steps, 100 after 10,000. This square root is the fingerprint of independent random additions — SGD noise (1/√batch), Monte Carlo error (1/√N) and Brownian motion's √dt.
Var(Sₙ) = n · SD = √n · B(t) ~ N(0, t)Add a random kick to gradient descent and the particle samples e^(−U/T). At T = 0 it is optimization; at high T it is a random walk. Mini-batch SGD is the same process with a noisy gradient, and diffusion models learn to run the noise backwards into data.
x ← x − dt∇U + √(2T·dt)·zA stochastic process is randomness that unfolds step by step, each step depending only on the last; the transition matrix (or the update rule) is the entire story, and the long-run behaviour is an eigenvector (or a stationary density) — which is how the same math powers MCMC, SGD, PageRank and diffusion models.
By the end you will be able to simulate random walks and check the √n law, read a transition matrix and find its stationary distribution by power iteration, estimate mixing from the spectral gap, compute hitting probabilities with gambler’s ruin, tell Poisson counts from exponential waits, simulate Brownian motion with the correct √dt noise, and explain why mini-batch SGD and diffusion models are stochastic processes you already know.
Static randomness is a coin flip. Sequential randomness is a process: each step depends on where you are now. That one rule — the Markov property — compresses an entire history into a single state.
A language model writes one token, then another, each conditioned on what it has already written. A diffusing image gets noisier step by step. A customer moves between active, at-risk and churned month after month. All three are stochastic processes: randomness that unfolds in time rather than sitting still.
The Markov property is the simplification that makes them tractable: the next state depends only on the current state, not on the path taken to reach it.
When the property holds, all the dynamics fit in a transition matrix P, where P[i][j] is the probability of moving from state i to state j. Every row sums to 1, because from state i you must go somewhere. And a distribution over states evolves by the row-vector product d ← dP — the same row-times-column rule as Lesson 02.
With states Sunny, Rainy, Cloudy the transition matrix is P = [[0.7, 0.1, 0.2], [0.3, 0.4, 0.3], [0.4, 0.2, 0.4]]. The stationary distribution solves πP = π with π₁ + π₂ + π₃ = 1 — π is a left eigenvector of P for eigenvalue 1. Solving the three equations gives exactly π = (6/11, 2/11, 3/11) ≈ (0.5455, 0.1818, 0.2727).
Second worked example, two states. Let P = [[1−a, a], [b, 1−b]] with a = 0.1 and b = 0.3: from state 1 you leave with probability 0.1, from state 2 with probability 0.3. The stationary distribution is π = (b/(a+b), a/(a+b)) = (0.75, 0.25). Check: 0.75·0.9 + 0.25·0.3 = 0.675 + 0.075 = 0.75 ✓ and 0.75·0.1 + 0.25·0.7 = 0.075 + 0.175 = 0.25 ✓. The eigenvalues are 1 and 1 − a − b = 0.6, so the distance to π shrinks by 40% per step: this chain mixes in about 2–3 steps. That second eigenvalue will matter in chapter 4.
Yesterday was rainy and today is rainy. To predict tomorrow's weather with a Markov chain, what do you need?
Start at 0. Flip a fair coin: heads move right, tails move left. The walk has no drift at all, yet it wanders further and further away — and the square root is the exact fingerprint of that wandering.
After n steps the position is the sum Sₙ = X₁ + X₂ + … + Xₙ, where each Xᵢ is +1 or −1 with probability ½. The expected position is 0 — the walk is perfectly fair. But the typical distance from the origin grows: about 10 after 100 steps, about 100 after 10,000 steps. Not 0, and certainly not 10,000.
Each step has variance 1 and the steps are independent, so variances add: Var(Sₙ) = n and the standard deviation is √n. The central limit theorem sharpens this: Sₙ/√n converges to a standard normal, so the endpoint after many steps is approximately Gaussian with mean 0 and SD √n. In two dimensions, four directions, the same law holds for the distance from the origin.
This square root is not a curiosity — it is the signature of independent random additions everywhere in ML: the noise in a mini-batch gradient shrinks as 1/√(batch size), Monte Carlo estimates improve as 1/√N, and embedding dimensions are scaled by √d.
Many walks at once, all seeded so the numbers are repeatable. The dashed curves are ±√n and ±2√n; the histogram on the right compares the final positions with the normal the CLT predicts.
Same square root, everywhere independence adds up: SGD noise shrinks as 1/√batch, Monte Carlo error as 1/√N.
After 10,000 fair coin-flip steps, roughly how far from the origin should you expect the walker to be?
A random walk does not just wander — we often need to know when it first reaches something, and which of two absorbing walls it reaches first. Those two questions have exact answers.
The hitting time (or first-passage time) of a level is the first moment the process arrives there. An absorbing state is a state you never leave — once the walk touches it, the clock stops. Churn, game over, the end-of-text token and a gambler leaving the table are all absorbing.
The cleanest version is gambler’s ruin: a walker starts at k, boundaries sit at 0 (ruin) and N (success), and each step goes up with probability p. For a fair coin the answers are beautifully simple: the probability of reaching N before 0 is k/N, and the expected number of steps until absorption is k(N − k). From k = 30 with walls at 0 and 100, that is a 30% chance of success and 2,100 steps on average.
A walker starts at k with absorbing walls at 0 and N. Run many seeded walks and compare the fraction that reach N, and the average duration, with the formulas from the chapter.
A 1% disadvantage drops the fair 30% win chance to about 4%: tiny drifts compound through the √n spread, which is the gambler’s ruin.
Probability. A fair walk is a martingale: its expected future position equals its current position. At the stopping time τ (when the walk first touches 0 or N) the position is either 0 or N, so E[S_τ] = P·N + (1 − P)·0 = P·N. Optional stopping says E[S_τ] = E[S_0] = k, hence P = k/N.
A 1% bias changes everything. Let p = 0.49, so q = 0.51 and r = q/p = 1.0408. The biased formula is P = (1 − rᵏ)/(1 − rᴺ). With k = 30, N = 100: r³⁰ ≈ 3.32 and r¹⁰⁰ ≈ 54.63, so P = (1 − 3.32)/(1 − 54.63) ≈ 0.043 — the fair 30% success chance collapses to about 4.3%. The expected duration from E = (k − N·P)/(1 − 2p) is (30 − 100·0.0433)/0.02 ≈ 1,284 steps: the unlucky walker is absorbed sooner, because ruin is now the likely outcome. Casinos do not need a big edge, only a persistent one.
One more exact fact. A 1D fair walk returns to its starting point with probability 1 — but the expected return time is infinite. The probability of a first return at step 2n decays like n^(−3/2), and when you weight that tail by n to compute a mean, the sum diverges. “Certain to happen, but with no finite expected wait” is the kind of sentence that only stochastic processes can produce.
Every well-behaved chain forgets where it began and settles into one long-run distribution. The where is an eigenvector; the how fast is an eigenvalue gap.
A stationary distribution π is a distribution that one transition leaves unchanged: πP = π. Read as a row vector times a matrix, that is exactly saying π is a left eigenvector of P with eigenvalue 1. It is the long-run fraction of time the chain spends in each state.
Two conditions make π attracting. The chain must be irreducible (every state reachable from every other) and aperiodic (no fixed-length cycle). When both hold, the chain is ergodic: no matter where it starts, the distribution converges to π, and time averages along one long trajectory equal averages over π. That equivalence is the reason MCMC works at all — one chain, run long enough, produces samples from the target.
How long is long enough? The spectral gap 1 − |λ₂| measures how fast the memory of the start decays. Distance to π shrinks roughly by |λ₂| per step, so the mixing time is about 1/(1 − |λ₂|) steps. Gap 0.2 → about 5 steps; gap 0.03 → about 33 steps; gap 0.001 → about 1,000.
Edit the transition table (each row is renormalized to sum to 1), pick a start state, and step the distribution forward. The stationary distribution π is computed by running the power method for 4,000 steps.
Sticky rows (0.98 on the diagonal) raise |λ₂| toward 1 and slow mixing; periodic rows keep the distance oscillating forever. π answers “how much time”, the gap answers “how soon”.
The stationary distribution is the fixed point of the update d ← dP, so simply iterating converges (the power method of Lesson 11). Starting from sunny, [1, 0, 0]:
The eigenvalues of the weather matrix are exactly 1, (5 ± √5)/20 ≈ 1, 0.3618, 0.1382. Check the trace: 1 + 0.3618 + 0.1382 = 1.5 = 0.7 + 0.4 + 0.4 ✓. The second eigenvalue is 0.3618, so the spectral gap is 0.6382 and the mixing time is about 1/0.6382 ≈ 1.6 steps — this chain forgets yesterday almost immediately.
The slow preset has a clean exact answer. P = 0.97·I + 0.01·J (where J is all ones) has rows (0.98, 0.01, 0.01) and so on. Its eigenvalues are 1 (on the all-ones direction) and 0.97 twice (on every zero-sum direction). The gap is 0.03, so mixing takes about 33 steps — 20× slower than the weather chain, by construction. The power-iteration readout in the lab recovers |λ₂| ≈ 0.970.
The periodic preset has π but no convergence. For P = [[0, 1], [1, 0]], π = [½, ½] satisfies πP = π, yet a chain started Sunny alternates forever: [1, 0], [0, 1], [1, 0], … and the distance to π never shrinks. The eigenvalue −1 sits on the unit circle; the chain is irreducible but period 2, so it fails the aperiodicity test.
A two-state chain has P = [[0, 1], [1, 0]] and starts in state 0. π = [½, ½] satisfies πP = π. Does the distribution converge to π?
Events that arrive independently at a steady average rate form a Poisson process. It answers two different-looking questions with two different distributions — and one memoryless rule ties them together.
A Poisson process counts independent events arriving at a constant average rate λ: photons hitting a sensor, requests reaching a server, customers entering a shop, radioactive decays. In a window of length t, the number of arrivals is Poisson(λt):
The time between arrivals is a different object: it is exponential with rate λ, density λe^(−λt), mean 1/λ. At λ = 2 per minute the average wait is 0.5 minutes. Exponential waits are memoryless: having already waited half a minute tells you nothing — the remaining wait has the same distribution as a fresh one. That is the continuous-time version of the Markov property from chapter 1.
Events arrive independently at average rate λ. The timeline shows one seeded run; the histograms compare the gap between arrivals with the exponential density and the count per minute with the Poisson pmf.
Counts and waits are two views of one process: the number of events in a window is Poisson, and the gap until the next event is exponential with mean 1/λ.
You arrive at a bus stop where buses come as a Poisson process averaging one every 10 minutes. You have already waited 10 minutes. What is the expected additional wait?
Shrink the step size as you add steps and the random walk converges to Brownian motion — a continuous process whose spread is a Gaussian, and whose density obeys the heat equation from physics.
Brownian motion B(t) is the continuous-time limit of the random walk: B(0) = 0; the increment B(t) − B(s) is normal with mean 0 and variance t − s; and increments on non-overlapping intervals are independent. The paths are continuous but nowhere differentiable — they jiggle at every scale, and a Brownian path drawn in the plane has fractal dimension 2.
To simulate it, remember the variance bookkeeping: over a small slice of time dt the position moves by √dt · z with z ~ N(0, 1). The square root is not cosmetic — it is what makes the variance accumulate at the right rate, and it is exactly the √n law in disguise. A cloud of diffusing particles in a fluid spreads with standard deviation √(2Dt), where D is the diffusion coefficient. (We set D = 1 below; real-world D depends on temperature, viscosity and particle size.)
That spreading density is the fundamental solution of the heat equation ∂u/∂t = D·∂²u/∂x²: the Gaussian bump above. The heat equation is the deterministic, macroscopic face of Brownian motion, and diffusion models are named after exactly this connection — their forward process is a discrete Brownian motion that grinds an image into noise.
√dt. Suppose each slice of length dt adds a kick of size c·z. Over total time t there are t/dt kicks, all independent, so the variance is (t/dt)·c². For the result to be t — the definition of Brownian motion — we need c² = dt, that is c = √dt. Numeric checks: with dt = 0.01, √dt = 0.1 and 100 steps give variance 100 × 0.01 = 1, so B(1) ~ N(0, 1); with dt = 0.0001, √dt = 0.01 and 10,000 steps give the same variance 1. Smaller slices, more steps, same process.
The heat kernel. The Gaussian u(x, t) = 1/√(4πDt)·e^(−x²/(4Dt)) has variance 2Dt. Plug it into ∂u/∂t = D·∂²u/∂x² and both sides agree; here is the numeric check at x = 0, t = 1, D = 1:
Notice how the same 2Dt appears in both stories: particles spread in both directions, so the variance grows twice as fast as the one-sided coefficient D alone would suggest. This is also the shape DDPM’s noising schedule imitates.
Add calibrated noise to gradient descent and the optimizer becomes a sampler. Mini-batch training already does this; diffusion models learn to run the whole noisy process backwards.
Langevin dynamics is gradient descent with a random kick at every step:
At T = 0 the noise vanishes and this is ordinary gradient descent. At very high T the landscape barely matters and the particle is a random walk. In between, it wanders but lingers in low-energy regions, and its long-run density is proportional to e^(−U(x)/T). Set U = −log p and T = 1 and the particle samples from p. That is the trick behind score-based generative models and SGLD (stochastic gradient Langevin dynamics), which turns an ordinary training loop into an approximate Bayesian posterior sampler: use a mini-batch gradient plus calibrated noise, decay the learning rate, and optimization quietly becomes sampling.
Mini-batch SGD is a stochastic process. Each step, the optimizer sees a noisy estimate of the true gradient — call it g + ε with noise SD proportional to 1/√B — so the parameter vector follows a random walk with a drift. Numeric check: going from batch 16 to batch 1,024 is 64× more data but only √64 = 8× less gradient noise, because the improvement is the square root of the batch ratio. When the noise is small the loss goes down; when it is large the parameters bounce around the minimum, which is why training curves are noisy and why noise can help escape shallow minima. The same temperature intuition applies: the effective “temperature” grows with the learning rate and shrinks with batch size.
Diffusion models are the same process in reverse. The forward chain (chapter 6, lab below) adds Gaussian noise for T steps until the signal is pure static. Generation runs a learned Markov chain backwards: a network predicts the noise ε that was added at each step, and each reverse step is one Gaussian draw using that prediction. Every DDPM sample is a trajectory through a transition matrix — just with millions of states.
A particle starts in the left well of U(x) = (x² − 1)² and follows x ← x − dt·∇U + √(2T·dt)·z with dt = 0.01. Turn the temperature knob and watch the balance between settling and hopping.
T = 0 is pure gradient descent; large T is nearly a random walk. The useful middle ground is why SGLD and score-based models use exactly this update.
Drift versus diffusion. Picture many particles. The gradient pushes them downhill at speed −∇U, while the noise spreads them out with strength T. At equilibrium the two flows cancel everywhere: drift carrying particles down the slope equals diffusion carrying them back up the density gradient, so −∇U·p = T·∇p. Rearrange to ∇(log p) = −∇U/T and integrate: log p = −U/T + const, hence p(x) ∝ e^(−U(x)/T). Low energy, high probability; temperature sets how much climbing the walker tolerates. Lesson 16’s softmax is the same formula with energy = −logit.
The forward diffusion step keeps variance at 1. Write one noising step as xt = √α·xt−1 + √(1 − α)·ε with independent standard noise, starting from a variance-1 signal. Then Var(x_t) = α·1 + (1 − α)·1 = 1: at every step the signal is replaced by noise rather than piled on top of it, so x_T approaches a clean N(0, I) no matter what the image was. With α = 0.99: ᾱ after 100 steps is 0.99¹⁰⁰ = 0.366, so the signal weight is 0.605 and the noise weight 0.796 — and after 1,000 steps ᾱ ≈ 4.0 × 10⁻⁵, essentially pure noise.
A 16 × 16 smiley is mixed with one fixed noise field: x_t = √ᾱ_t·x₀ + √(1 − ᾱ_t)·ε with a linear schedule over 1,000 steps. Drag the timestep or press play.
This is the chain DDPM runs forward. Generation runs a learned network backwards: predict ε, subtract part of it, repeat.
Answer before you look. The √n and stationary-distribution questions are the ones that separate “I’ve seen randomness” from “I can predict it”.
0 / 5 answered · 0 correct
01What is the Markov property?
02In a 1D random walk, how does the expected distance from the origin scale with the number of steps n?
03What is the stationary distribution of a Markov chain?
04In Langevin dynamics x_{t+1} = x_t − dt·∇U(x_t) + √(2T·dt)·z, what happens as temperature T approaches 0?
05In a diffusion model, what does the forward process do to a data sample over T steps?
Click a card to swap the lazy description for what it actually means.
Five problems, all worked with numbers you can reproduce in the labs. Try first; the answer is one click away.
Using the lab's mulberry32 RNG with seed 42: sample mean −3.34 (expected 0; the mean of 1,000 independent endpoints has SD 100/√1000 ≈ 3.16, so this is about one SD of zero), sample SD 101.05 (expected 100), 67.9% of endpoints inside ±100 (a Gaussian gives 68.3%) and 95.4% inside ±200 (Gaussian 95.4%). The histogram is the classic N(0, 100) bell. Why: each endpoint is a sum of 10,000 independent ±1 steps, so the central limit theorem forces a Gaussian, and variances add to give Var = 10,000 and SD = 100. One caveat to notice: positions after an even number of steps are always even, so a coarse histogram is comb-shaped — with 10,000 steps the spacing of 2 is invisible next to an SD of 100. The sample SD itself has uncertainty ≈ SD/√(2·999) ≈ 2.2, so 101.05 is well within noise.
Corpus: “the cat sat on the mat”, “the dog sat on the log”, “the cat ate the fish”. Add a stop token END. From “the” the transitions are cat ×2, dog, mat, log, fish — six counts total, so P(cat | the) = 2/6 ≈ 0.333 and each other = 1/6 ≈ 0.167. Check the row sums: 0.333 + 5 × 0.167 ≈ 1.00 ✓. Other rows: P(sat | cat) = 1/2, P(ate | cat) = 1/2; P(on | sat) = 1, P(the | on) = 1; P(END | mat) = P(END | log) = P(END | fish) = 1. Greedy generation (always take the most likely transition) walks “the → cat → sat → on → the → mat → END”, i.e. “the cat sat on the mat.” Sampling with a seeded RNG produces the same grammar with different nouns: “the dog sat on the log” or “the cat ate the fish”. Two practical notes: every unseen transition has probability 0 and can never be generated (add-1 smoothing fixes that), and the chain is memoryless, so a sentence's next word depends only on the current word — that is why word-level Markov text is grammatical locally and incoherent globally. Letter-level chains behave the same way.
The algorithm: propose x' near the current x, compute ΔU = U(x') − U(x), and accept with probability min(1, e^(−ΔU/T)). Numeric checks: an uphill proposal with ΔU = +1 is accepted with probability e^(−1/T) — 0.368 at T = 1 (barely biased), 4.5 × 10⁻⁵ at T = 0.1, and about 3.7 × 10⁻⁴⁴ at T = 0.01; a downhill proposal (ΔU < 0) is accepted with probability 1 at every temperature. With a cooling schedule like T_step = 0.9^step, T falls from 1.0 to 1.0 × 0.9⁵⁰ ≈ 0.005 in 50 steps, so the chain is exploratory early and essentially greedy late. The temperature schedule is the whole trick: stay hot long enough to cross barriers, then cool to settle. Deterministic check of the schedule: after 22 steps T = 0.9²² ≈ 0.098, and e^(−1/0.098) ≈ 3.7 × 10⁻⁵, so uphill moves have all but stopped.
The stationary density is p(x) ∝ e^(−U(x)/T). U has minima at ±1 with U = 0 and a barrier of height U(0) = 1, so p(0)/p(±1) = e^(−1/T): 0.0357 at T = 0.3 (the barrier is 28× less likely than a well) versus 0.3679 at T = 1 (only 2.7× less likely). The well is symmetric, so once the chain mixes, both wells hold 50% of the time at every temperature — the difference is whether it mixes. Seed-5 run from x = −1, dt = 0.01, 20,000 steps: at T = 0.3 there were 29 crossings of x = 0 and the histogram filled only the starting well; at T = 1 there were 336 crossings and the histogram matched e^(−U/T) across both wells. The crossing rate has the Kramers form (prefactor × e^(−ΔU/T)), so mixing becomes common only when T is on the order of the barrier height 1; at T = 0.3 a crossing costs a factor e^(−1/0.3) ≈ 0.036, which is why the run looks frozen. Lesson: low temperature means precise but slow — the same trade-off as MCMC proposal tuning.
Use x_t = √(ᾱ_t)·x_0 + √(1 − ᾱ_t)·ε with ε ~ N(0, 1), where ᾱ_t is the running product of α_t = 1 − β_t. Numeric checks with a linear schedule β from 0.0001 to 0.02 over 100 steps: ᾱ_100 ≈ 0.364, so at the last step the signal is multiplied by √0.364 ≈ 0.603 and the noise by √(1 − 0.364) ≈ 0.798; with a constant α = 0.99 instead, ᾱ = 0.99^100 ≈ 0.366 and the weights are 0.605 / 0.796 (the two schedules agree to two decimals because ᾱ ≈ e^(−Σβ)). The variance stays exactly ᾱ + (1 − ᾱ) = 1 at every step: signal is replaced by noise, not added on top of it. Notice that 100 gentle steps do not yet destroy the sine — 36% of the variance is still signal. The lab stretches the same linear schedule to the DDPM-sized 1,000 steps: ᾱ_1000 ≈ 4.0 × 10⁻⁵, signal weight ≈ 0.006, so x_1000 is pure static. A naive denoiser x̂_0 = x_t/√ᾱ_t has error standard deviation √((1 − ᾱ)/ᾱ) = √(0.636/0.364) ≈ 1.32 at t = 100 — larger than a unit-amplitude sine, so dividing cannot recover it; the real reverse process trains a network to predict ε from (x_t, t) and subtracts a calibrated fraction of it, one small step at a time. That is why DDPM generation takes hundreds of network calls instead of one.
You do not need to master these here. Each one gets a proper treatment in its own lesson; the one-line meaning is enough to keep reading. Orange dotted underlines in the prose point back to this list.
This lesson is a port of an open course. Everything here traces back to it — and the next step is running the code yourself.
Lesson text adapted from AI Engineering from Scratch (Phase 01, Lesson 22) and the Math Foundations Notebook reference build. The random-walk envelope lab, Markov chain power-iteration lab, gambler's-ruin lab, Poisson arrivals lab, Langevin double-well lab and forward-diffusion preview are original to this page, as are the exact weather-chain eigenvalues 1, (5 ± √5)/20, the sticky-chain |λ₂| = 0.97, the customer-churn expected lifetimes, the biased gambler's ruin numbers, the exponential memorylessness check, the heat-kernel numeric check and the fully worked exercise answers. Every stochastic simulation is seeded with the same mulberry32 generator the text quotes, so the numbers are reproducible in your browser.