Experiment № 082 · The story
The Likeliest Story
Why I picked it
I kept meeting the same sentence in textbooks — the most likely sequence of states is not the sequence of most likely states — nodding at it, and not really believing it. So I built the smallest thing that makes it undeniable. A walker drifts along a corridor of ten rooms, one door per step, and every door is painted one of a handful of colours. A sensor calls out the colour of the room the walker is in, and lies about one time in five. No single reading can tell you where anyone is: several rooms share every colour. But the run of colours is very nearly a fingerprint. Andrew Viterbi's 1967 algorithm — written for decoding convolutional codes, and now sitting in phones, disk read channels, speech recognisers and gene finders — is how you cash that in.
What I enjoy about it
The forgetting. Each column keeps exactly one route into each room — the best one — and discards every other way of arriving, forever, because no future evidence could ever promote a worse prefix. That is the whole trick, and it turns a number of possible walks with eighteen digits in it into a hundred comparisons per step. Then turn on draw every surviving path and watch the second delight: the ten survivors differ only near the cursor, and behind it they collapse into a single trunk. Once every survivor agrees about step 40, nothing that happens later can change step 40 — which is exactly why a hardware decoder can hold a fixed window of history and stream forever. Hovering a cell shows the one story that ends there; the table is ten stories being edited in parallel, and nine of them get abandoned.
Something you might take away
A chain of individually best decisions is not the best chain. Watch the scoreboard and you will see the pink line — the best guess for each step on its own, worked out from the whole recording — name more rooms correctly than the violet one. It should: that is the metric it optimises, one room at a time. And it is still not a story. Every few runs it steps from room 3 to room 7 in a single tick, through doors that do not exist, because nothing ever asked it to be a sequence. So: if your answer has to hold together, score whole answers, not steps. Two smaller things I took away. The constraint is free — one door per step is one more term in a sum, and it is what rescues a hopeless sensor. And everything runs in logarithms, because multiplying enough probabilities together underflows to zero; once it is all addition and comparison, this stops looking like statistics and starts looking like what it is — a shortest path through a layered graph.