← mino.mobi

markov

markov chains · MCMC · the markov numbers

↑ geometry pack · the engine room behind temperley–lieb & aztec

Two unrelated gems, both Andrey Markov's. On one side, Markov chains — memoryless random processes that forget where they came from, and the engine (MCMC) behind every thermostat on the sibling pages. On the other, the Markov numbers — a Diophantine tree hiding inside how badly you can approximate a number. Same man, 1906 and 1879; nothing else in common.

A Markov chain hops between states, each step depending only on where it is now. Drop the walker and watch the bars: the fraction of time it spends in each state converges to the stationary distribution π — no matter where it started. How fast it forgets is set by the spectral gap; the two clusters chain barely connects, so it mixes painfully slowly (a tiny gap). Click a state to teleport the walker there.

chain
laziness (self-loop prob)
0.00
speed · updates / sec
6
Bars: filled = empirical visit frequency, outline = stationary π (computed as the left eigenvector πP = π). |λ₂| is the second-largest eigenvalue magnitude — the closer to 1, the slower the chain mixes; the relaxation time is 1/(1−|λ₂|).

Design a 2-D distribution as a mixture of Gaussians — click empty space to drop one, drag to move it, shape it (width, height, tilt, weight). Then sample it exactly (i.i.d. — the right tool for a mixture, and what you'd feed a Monte Carlo) or watch Metropolis wander in and converge to the same density. Export the samples as CSV/JSON, or copy a one-line call that returns them from the /markov-sample API.

sampler
target sample count · N
2000
metropolis proposal · σ
0.60
selected Gaussian — click one
σx0.60
σy0.60
tilt0.00
wt1.0
export cleanup (metropolis) — burn-in / thin
500
10
speed · updates / sec
20
export
Exact sampling draws each point independently — clean i.i.d. samples, no warm-up. Metropolis produces a correlated chain, so its export applies burn-in (drop the warm-up) and thinning (keep every k-th) to recover near-independent samples. The API call POSTs your spec to /markov-sample and returns exact samples server-side.

A random walk is the simplest Markov chain: step to a random lattice neighbour, forever. Pólya's theorem (1921) says something startling — in 1 and 2 dimensions the walk is recurrent (it returns to the origin with probability 1), but in 3 dimensions it is transient: it wanders off and may never come back. "A drunk man will find his way home, but a drunk bird may get lost forever." Watch the return fraction climb to 1 — or stall near Pólya's constant 0.34.

dimension
walkers
500
Each dot is an independent walker; a walker glows once it has revisited the origin. The return fraction is the share that have made it home at least once. As the clock runs it →1 in 1-D/2-D but plateaus near 0.3405 in 3-D — the Pólya return probability.

The Markov chain everyone has met: feed it text, and it learns, for each short run of characters, what tends to come next. Generate by hopping that chain. At order 1 it's gibberish with the right letter frequencies; crank the order up and English crystallises out of pure statistics — words, then phrases — with no grammar, no dictionary, nothing but "what followed what."

corpus
order · n (context length)
3
Character-level model: the context is the last n characters, and the next character is drawn from those that followed that exact context in the corpus. Order 1–2 ≈ letter soup; 4–6 ≈ almost-words and real phrasing; 8 starts quoting the source verbatim (the model overfits).

The other Markov. Solutions of x² + y² + z² = 3xyz in positive integers — the Markov triples — form an infinite binary tree rooted at (1,1,1). Fix two coordinates and the equation is a quadratic in the third with a second root z′ = 3xy − z (Vieta jumping): every triple has neighbours, and climbing away from the root grows them forever. The values that appear — 1, 2, 5, 13, 29, 34, 89, 169, … — are the Markov numbers. Click any node to inspect its triple.

tree depth
5
The stem 1,1,1 → 1,1,2 → 1,2,5 is unbranched; from (1,2,5) on, each triple has two children (the two Vieta jumps that increase the largest entry). The famous open unicity conjecture (Frobenius, 1913) asks whether the largest entry determines the whole triple — i.e. whether every Markov number appears exactly once in the tree. Verified past 1050, still unproven.

Here's where the two Markovs almost touch. "How badly can an irrational be approximated by fractions?" has an answer for each number — its Lagrange number — and the set of all of them is the Markov spectrum. Below 3 it is discrete: a ladder indexed exactly by the Markov numbers, Lm = √(9m²−4) / m, climbing √5, √8, √221/5, … toward 3 but never reaching it. The golden ratio (m = 1, L = √5 ≈ 2.236) is the single worst-approximable number there is. Hover a rung.

Top: the ladder, evenly spaced so you can read it — every rung is a Markov number, rising to the dashed ceiling at 3. Bottom: the spectrum on a true axis, where the ladder crowds against 3, a complicated zone of gaps follows, and from Freiman's constant ≈ 4.5278 onward it is a solid ray (Hall, 1947). m = 1 ↔ φ = [1;1,1,…]; m = 2 ↔ 1+√2 = [2;2,2,…]; the rest are periodic blocks of 1s and 2s (Markov's theorem).

Two Markovs

Andrey Andreyevich Markov (1856–1922) lends his name to two things on this page that have nothing to do with each other. The Markov chains came late (around 1906), when he studied sequences of dependent random variables — partly, the story goes, to win an argument about whether the law of large numbers needs independence. (It doesn't.) The Markov numbers came early (1879–1880), from his thesis on indefinite quadratic forms. Both are below; the number-theory half arrives in the next pass.

Chains and the stationary distribution

A Markov chain is a walk on states where the next state depends only on the current one — the memoryless property. Encode it as a transition matrix P with P[i][j] the probability of going i→j (rows sum to 1). If the chain is irreducible (you can get anywhere) and aperiodic (no rigid cycle), there is a unique stationary distribution π with πP = π, and the fraction of time spent in each state converges to π from any start. That's the ergodic theorem, and it's what the chain tab shows: the bars climb to π and stay.

How fast? The transition matrix's eigenvalues are 1 = λ₁ > |λ₂| ≥ …; the gap 1−|λ₂| is the spectral gap, and the chain forgets its start on a timescale of 1/(1−|λ₂|). The two clusters preset wires two tight groups with one thin bridge: |λ₂| sits just under 1, the gap is tiny, and mixing takes forever — the same bottleneck that makes glassy physical systems hard to simulate.

MCMC: running a chain backwards

Usually you have a chain and want its stationary π. Markov chain Monte Carlo flips that: you have a distribution π you want to sample (a Gibbs measure, a posterior, a density you can only evaluate up to a constant) and you design a chain whose stationary distribution is exactly π. The Metropolis rule does it with one trick: propose a move, accept with probability min(1, π(new)/π(old)). The ratio kills the unknown normalising constant, and detailed balance guarantees π is stationary. Every thermostat on temperley–lieb — Metropolis spin flips, Swendsen–Wang clusters, the tortuosity backbite, the Aztec shuffle — is an MCMC sampler in this exact sense.

Recurrence: Pólya's theorem

The plainest chain is the simple random walk on the integer lattice. Pólya (1921) found a sharp dimensional divide: the walk returns to its start with probability 1 in dimensions 1 and 2 (recurrent), but in dimension 3 the return probability drops to about 0.3405 (transient) — and keeps falling in higher dimensions. The walk tab races hundreds of walkers and watches the return fraction confirm it: home in the plane, lost in space.

Text and the original application

Markov's own first application of his chains was to text: he counted vowel/consonant transitions across 20,000 letters of Pushkin's Eugene Onegin. The text tab is the same idea at full resolution — an n-gram model where the next character is drawn conditional on the last n. It is the ancestor of every autocomplete and, in spirit, of the large language models that followed: more context, better statistics, and language emerges with no rules written down.

The Markov numbers

The early Markov, from his 1879 thesis: the positive-integer solutions of x² + y² + z² = 3xyz. The trivial one is (1,1,1); the equation is a quadratic in each variable, so given two coordinates the third has a partner root z′ = 3xy − z — a Vieta jump. Jumping repeatedly generates every solution, and they hang on a binary tree: 1,1,1 → 1,1,2 → 1,2,5, then forks forever. The numbers that show up as coordinates — 1, 2, 5, 13, 29, 34, 89, 169, 194, 233, … — are the Markov numbers, and two famous spines run up the tree: the odd-indexed Fibonacci numbers (1,5,13,34,89,233,…) and the odd-indexed Pell numbers (2,5,29,169,985,…). The tree tab grows it; the unicity conjecture — that the largest entry names the triple uniquely — is still open after a century.

… and the spectrum that connects them

Now Markov's actual theorem, the bridge to approximation. By Hurwitz, every irrational α has infinitely many rationals with |α − p/q| < 1/(√5 q²), and √5 is best possible — the golden ratio achieves it and nothing beats it. But if you exclude the golden ratio and its equivalents, the constant improves to √8; exclude those too and it jumps to √(221)/5; and so on. Markov proved these record constants are exactly Lm = √(9m²−4)/m, indexed by the Markov numbers — the same 1, 2, 5, 13, … from the tree. This discrete ladder, climbing to 3, is the bottom of the Lagrange/Markov spectrum; above 3 lie gaps, and past Freiman's constant ≈ 4.5278 the spectrum is a solid ray (Hall). The extremal numbers have continued fractions built from just 1s and 2s. The spectrum tab plots the ladder and the ray.

sources