Type "good" on your phone and it offers morning, night, luck. It hasn't read your message. It looked at one word, the last one, and remembered what usually comes next.
That's a strange kind of memory: it forgets everything except right now. Yet it is good enough to finish your sentences, rank every page on the web, and tell your map which road you are on.
Last issue ended with a lazy frog whose averages piled up in a hill 2.3 times wider than they should have. The frog had this same one-step memory. This issue follows the frog, and by the end that 2.3 will make sense.
Message
Follow the frog
Three lily pads, numbered 1, 2 and 3, and one lazy frog. Every second it makes one choice:
- 8 times out of 10 it stays where it is.
- Otherwise it jumps to one of the other two pads, either one.
That's all. It doesn't remember where it was yesterday, or how long it has sat still. Only the pad under its feet matters.
Watch the tally below the pond. Early on it's lopsided, because the frog sits on one pad for a while. Leave it running and each pad's share creeps toward a third, the orange line.
A memory of one step, and still the counts settle. They just take their time.
Share of time on each pad
You already know this game
In Snakes and Ladders you're on square 34 and you roll a 4. Does it matter how you got to 34, up a ladder or down a snake? No. Your square and the die decide everything. The game forgets your past at every turn.
The frog works the same way. Its "square" is its pad, and its "die" is the 8-in-10 chance of staying put.
Now build your own pond. Each slider says how sticky one pad is: how often the frog stays there. The rest of the time it jumps to one of the other two. The table shows the rules. The strip shows the frog's last 240 hops, one pixel per hop, and the bars show where it spent its time.
Make pad 1 very sticky and the others slippery. The frog ends up living on pad 1, because you spend the most time where you linger longest. Change the starting pad: the bars still end up in the same place.
The frog's path, one pixel per hop
Share of time on each pad, over 5,000 hops
| From | → 1 | → 2 | → 3 |
|---|
What it actually says
The future only cares about now.
Anything that moves between a few states, where the chance of the next state depends only on the current one, is called a Markov chain. The states can be lily pads, board squares, words, web pages or the weather.
A chain is completely described by its table of rules: from each state, the chance of each next state. The lazy frog's table:
| From | To pad 1 | To pad 2 | To pad 3 |
|---|---|---|---|
| Pad 1 | 80% | 10% | 10% |
| Pad 2 | 10% | 80% | 10% |
| Pad 3 | 10% | 10% | 80% |
Run any chain long enough and the share of time in each state stops changing. That's the long-run share, and it doesn't depend on where you started. It settles because, eventually, just as many hops flow into each pad as flow out of it.
So the law of large numbers survives memory: averages still arrive at the truth. That was exactly what Andrey Markov set out to prove.
The precise version (skippable)
Write the rules as a table P, where P(i → j) is the chance of hopping from state i to state j. If π lists the long-run share of each state, then one more hop changes nothing:
π(j) = Σᵢ π(i) · P(i → j) for every j, or in short πP = π
If every state can reach every other and the chain doesn't cycle in a fixed rhythm, there is exactly one such π, the chain's share of time converges to it from any start, and averages along the chain converge to averages under π. For the pond with the sliders, the answer is simple: pad i's share is proportional to 1 ÷ (1 − its stickiness), the average length of one visit.
Where it came from
It started with an argument. In 1902 Pavel Nekrasov claimed that averages only settle if the events don't affect each other. In 1906 Andrey Markov proved him wrong, with chains of events that each depend on the one before. In 1913 he showed a real one: he went through the first 20,000 letters of Pushkin's poem Eugene Onegin by hand, marking each as a vowel or a consonant. A vowel was usually followed by a consonant, yet over the whole poem about 43% of letters were vowels, just as his chain predicted.
Above: 400 letters drawn by the page from Markov's own counts. Dark squares are vowels.
Claude Shannon uses chains of letters and words to make fake English that gets more convincing the more it remembers. It's the ancestor of every text generator.
Sergey Brin and Larry Page rank the web with a random surfer clicking links. The idea becomes Google.
How fast it forgets
Put 1,000 frogs on pad 1 and let them all hop at once. After one hop, 80% are still there. After a few more, the crowd spreads out, until each pad holds about a third.
For the lazy frog, the extra crowd on pad 1 shrinks by 0.7 every hop: 0.8 for staying, minus 0.1 for landing back by chance. After 10 hops, 35% are on pad 1, close to a third. Make the pads stickier and the frogs forget more slowly.
Now the 2.3 from last issue. Averaging 50 hops of a frog that mostly stays put is like asking 50 people when most of them repeat what their neighbour said. You don't really have 50 opinions. Here is what 50 hops are worth:
| The frog stays | 50 hops are worth | Hill width |
|---|---|---|
| 1 time in 3 (no memory) | 50 samples | 1× |
| 5 times in 10 | 30 samples | 1.3× |
| 8 times in 10 | 9 samples | 2.3× |
| 95 times in 100 | 3 samples | 4.4× |
Fewer real samples, wider hill. The lazy frog's 50 hops carry about as much information as 9 independent ones, and that's the whole 2.3.
Where the 1,000 frogs are now
Share still on pad 1, hop by hop
Read the small print
"Settles to a long-run share" is a promise with conditions. Each failure below loads into the pond builder above, so you can watch it break.
What it promises
- Start anywheresame answer
Where the frog begins stops mattering. The pond decides, not the start.
- Averages still settlejust slower
Memory doesn't break the law of large numbers. It only means you need more hops than you'd think.
- You can predict the sharefrom the rules
The table alone tells you the long-run share, before the frog makes a single hop.
Where it breaks
- Trapsnever leaves
Square 100 in Snakes and Ladders: once you're there, the game is over. A pad the frog never leaves swallows everyone, wherever they started.
- Endless loopsno rest
A frog that always goes 1 → 2 → 3 → 1 spends a third of its time on each pad, but ask where it is at hop 1,000 and the answer never settles. It just depends on the count.
- Cut-off pondsstart decides
If no hop leads from pads 1 and 2 to pad 3, they are two separate ponds. Where you start decides where you live, forever. Try each starting pad.
- One step is an assumptionreal life remembers
Weather, people and sentences remember more than one step back. A chain that only looks at the last word writes nonsense. Give it more memory and it improves, as "Build it" shows.
Build it
Here is a text-writing machine in about 15 lines. It isn't a copy: the page reads this function out of its own script and runs it on the screen beside it.
Two steps. First, count: for every "now" (the last word, or the last two), make a list of the words that came next in the text. A word that followed twice is in the list twice. Second, babble: look at the current "now", pick from its list at random, and repeat.
Picking from a list with repeats is how the machine follows the counts: a word that came next 3 times is 3 times as likely to be picked. With a memory of one word the result is word salad. With two, whole phrases come back. Paste in any text you like.
Where it runs today
Where it runs today
Links: A → B, C · B → C · C → A · D → A, C · E → D
A frog on an endless row
Last one. Take away the pond and give the frog an endless row of pads. Every second it hops one pad left or one pad right, like a coin toss. No stickiness, no memory beyond where it is.
Release 1,000 frogs from the middle and see where they are after some hops.
Where the 1,000 frogs ended up
Coins, dice, polls, and now frogs. Every time, the same hill. Why does this one shape keep showing up? That's the next issue.