Random Processes: After 10,000 Steps You're on Average 80 Squares From Home (AI Engineering Foundations #22)

Forum topic · 小凯 · 2026-10-17

Summary

Lesson 22 of the open-source 'AI Engineering Foundations' series (58k stars) walks through random processes—random walks, Markov chains, Metropolis-Hastings, Langevin dynamics, and diffusion models—in a single thread, while auditing the course's own claims. Key corrections: after 10,000 ±1 coin-flip steps, the expected absolute distance from origin is ~79.8 (not 100; 100 is the standard deviation, verified by simulation at 79.7). For Markov chains, the stationary distribution equals the eigenvector with eigenvalue 1, and the spectral gap governs mixing speed. The author clarifies in what sense LLM token generation is Markovian: state is the entire context window, truncated by finite context length. On sampling, the famous 23% optimal Metropolis acceptance rate is a high-dimensional asymptotic result—1D experiments here show 44% maximizes effective sample size (step size 2.4 vs. 0.5 or 6). Langevin dynamics simulations of a double-well potential show Kramers-style exponential barrier crossing (0, 0, 6, 28, 133 crossings as temperature rises). Finally, the article verifies the diffusion forward process's closed-form x_t formula recovers the original image to machine precision (error 4×10⁻¹⁶), and flags that default β schedules leave ᾱ = 0.36, far from pure noise.

Random Processes: Walk 10,000 Steps, End Up on Average 80 Squares From Home

This is lesson 22 of the AI Engineering Foundations series (ai-engineering-from-scratch by Rohit Ghumare, MIT license)—a 58k-star open-source course that disassembles the math behind AI, and the final lesson of the season's math foundations track. It covers random walks, Markov chains, Metropolis-Hastings, Langevin dynamics, and diffusion models as one continuous story—along with a careful audit of where the course's own numbers slip.

Key points

1. Random walks: RMS distance ≠ expected distance

Start at 0 on the number line; each coin flip moves ±1. After 10,000 steps:

Expected position = 0, but you'll almost never actually be there.
Variance adds across independent steps: 10,000 → standard deviation = √10000 = 100 (the RMS distance).
The expected absolute distance is a different question. Because squaring inflates large deviations, direct averaging gives 79.8 = 100 × √(2/π).

The author's simulation (2,000 walks of 10,000 steps): mean |position| = 79.7, std = 99.8 — matching theory. The 2D version (four directions): mean distance 88, RMS 100, factor 0.886.

The course text labels the 100 as "expected distance from origin" — a mislabel. Using the standard deviation as the mean distance inflates budgets (robot search radii, asset volatility scales) by ~25%. Notably, the course's own exercise hint uses 100 correctly as a standard deviation (68% coverage check; measured 68.9%). A gambler's-ruin check also holds: starting with $25, quitting at $100 or $0, the fair-game win probability is exactly 25/100 (simulated: 0.248) — a consequence of fair walks being martingales.

2. Markov chains, stationary distributions, and the spectral gap

A weather example (sunny/rainy/cloudy, 3×3 transition matrix) converges to a stationary distribution independent of the starting state: exactly 6/11, 2/11, 3/11 (0.545, 0.182, 0.273) — the eigenvector of the transition matrix with eigenvalue 1.

Convergence speed is governed by the spectral gap = 1 − (second-largest eigenvalue). The weather chain's second eigenvalue is 0.36; after 15 steps from pure rain, deviation from stationarity < 10⁻⁶.
The course's spectral-gap code ([[0.9, 0.1], [0.3, 0.7]]) gives eigenvalues 1 and 0.6, gap 0.4, mixing time ≈ 2.5 steps — while the prose quotes numbers (0.2, five steps) from an unrelated matrix.
Strictly, 1/spectral-gap is the relaxation time (decay to 1/e); the rigorous mixing time adds a logarithmic factor.
Practical ML relevance: the spectral gap tells you how much burn-in a sampling chain needs before samples are worth collecting.

3. How language models are (and aren't) Markovian

With state = "last token": not Markov — the next-token distribution depends on the whole prefix.
With state = "entire context": exactly Markov, since all earlier history already sits inside the state.
The real approximation is context truncation: the state space is too large, so the chain is used with a finite window.
Temperature reshapes transition probabilities (sharper below 1, flatter above); top-k / top-p truncate the transition table directly.

4. Metropolis-Hastings: the 23% rule is high-dimensional

M-H builds a Markov chain whose stationary distribution is the intractable target (e.g., a Bayesian posterior); all computations use probability ratios, so the unusable normalizing constant cancels. The course's bimodal experiment (peaks at ±3) works: over 100k proposals, 49.77% left / 50.23% right.

But the famous "target ~23% acceptance rate" is the asymptotic high-dimensional result (Roberts, Gelman & Gilks, 1990s); the same literature gives ~44% for one dimension — and all the course's demos are 1D. Scanning proposal step sizes against a standard normal target:

| Step size | Acceptance | Effective sample size | |---|---|---| | 0.5 | 84% | < 900 | | 2.4 | 44% | 4,500 (best) | | 6 | 21% | −40% vs. best |

The repo's own parameter sweep (54% acceptance at step 2.0 performing best) corroborates the 44% target.

5. Langevin dynamics: optimization + noise

One update rule welds gradient descent and sampling together: step along the negative gradient, then add a random kick. At equilibrium the particle's position distribution ∝ exp(−Energy), spending more time in low-energy regions. In the double-well exercise, E(x) = (x² − 1)² with barrier height 1, counting zero-crossings over 100k steps from the right well:

| Temperature | 0.05 | 0.10 | 0.15 | 0.20 | 0.25 | |---|---|---|---|---|---| | Crossings | 0 | 0 | 6 | 28 | 133 |

Barrier crossing is exponentially suppressed (the Kramers escape rate: barrier/temperature sits in the exponent) — the same wall governs mode-hopping in diffusion sampling and annealing schedules.

6. Diffusion models: walk the noise in, walk it back out

The forward process is discrete Brownian motion: each step scales the signal by (1−β) and adds noise. Purity of the final noise is judged by ᾱ, the product of all (1−β):

Course defaults (β: 0.0001 → 0.02, 100 steps): ᾱ = 0.36; measured correlation with the original image 0.58 — far from pure noise.
Repo demo (β up to 0.05): ᾱ = 0.075, correlation 0.29 — yet the demo claims "nearly pure noise." By the course's own criterion, raising β's terminal value to 0.2 gives ᾱ ≈ 2×10⁻⁵, correlation 0.09.
The forward process has a closed form: x_t = √ᾱ · x₀ + √(1−ᾱ) · ε. Inverting it recovers x₀ to machine precision (error 4×10⁻¹⁶) — algebra, not statistics: the noise added is exactly the noise stored. The network's real job is the reverse: guessing what to subtract from unseen noise.

Wrap-up

Twenty-two lessons close the math foundations season. Exercise 4 invites readers to sweep temperature from 0.05 to 1.0 and watch the barrier-crossing counts — 0, 0, 6, 28, 133 — to find when their own wall turns into a door.

(Source: ai-engineering-from-scratch, Rohit Ghumare, MIT license.)