Randomness:
the power of guessing

You want to know the average height of the million people in your city. The thorough approach is to measure a million people. The other approach is to measure a hundred people picked at random — and you'll be off by about a centimetre.

Sit with that ratio for a second. One ten-thousandth of the work buys you virtually all of the answer. Not a rough gesture at the answer: a number with a stated error bar that shrinks predictably as you measure more (like most of statistics, it shrinks with the square root of your sample, so quadrupling the effort halves the error — which is exactly why measuring a million people is such a terrible deal).

This is sampling, and the part everyone gets backwards is why the randomness matters. It's tempting to think a thoughtfully hand-picked "representative" hundred would do better than a hundred random strangers. It does worse, reliably, because a hand-picked sample carries your assumptions about what representative means — and those assumptions are exactly the thing you were trying to measure. A random sample has no opinion. Its errors are noise, and noise averages out. Your errors are bias, and bias doesn't.

In 1946 Stanislaw Ulam was home sick from Los Alamos, playing solitaire, and idly wondered what fraction of deals are actually winnable. Being one of the best mathematicians alive, he tried to work it out. The combinatorics ate him alive — the number of card orderings is astronomical and the play tree branches at every turn. There is no clean formula, and there was never going to be one.

So he gave up on the formula and had the thought that founded a discipline: just deal a hundred hands and count how many you win.

That's it. That is the entire method. It went straight from a sickbed card game into the neutron-diffusion calculations for the hydrogen bomb, and from there into finance, weather, graphics, drug design, and the estimator in your A/B testing library. Ulam's colleague Nick Metropolis named it after the casino in Monaco where Ulam's uncle used to gamble, which is the most honest name any algorithm has ever been given. It's the Monte Carlo method, and the lesson is one line long: when a system is too tangled to analyse, run it and watch.

Here's the version you can play with. π is defined by a perfectly clean piece of geometry, and we're going to find it by throwing darts at a wall like an idiot. Throw a dart uniformly at the square; the fraction landing inside the quarter-circle is the ratio of their areas, which is (πr²/4) / r² = π/4. So four times the hit rate is π. No calculus, no series, no cleverness — just counting.

Sampling gives you an estimate. That feels fine for heights and card games. Now here's the uncomfortable one: is this 300-digit number prime? That's not a question you estimate. It's a yes or a no, and the whole internet is standing on the answer.

Checking it properly means trying to divide by everything up to its square root. For a 300-digit number that's about 10¹⁵⁰ divisions. The universe contains roughly 10⁸⁰ atoms. You could turn every atom into a computer and you would not finish. Certainty, here, is not expensive — it is unavailable.

So do something else: poke the number. Pick a random number under 300 digits and put it through a short arithmetic ritual — a specific little dance of squarings and multiplications, mod n — that every genuine prime is guaranteed to survive. If your number stumbles, it is definitely composite, no doubt, no appeal, and you know this without ever finding a factor. If it survives, you've learned something weaker: this particular random poke found nothing.

The magic is in the guarantee. For any composite number, at least three-quarters of the possible pokes catch it. So a composite that survives one random poke got lucky at 1-in-4. Surviving twenty is 1-in-4²⁰ — about a trillion to one. Surviving a hundred is 1-in-10⁶⁰. That is the Miller-Rabin test, and it turns "I cannot possibly know" into "I know, with a probability of error I get to choose."

And now the delightful part. Every https connection you have ever made rests on large primes. Those primes were not proved prime. They were poked forty-ish times and waved through. We looked certainty in the eye, checked the price, and bought 1-in-2⁸⁰ instead — and it has been completely fine, because at those odds the failure mode isn't "the maths was wrong," it's "a cosmic ray flipped a bit in your CPU and you got the wrong answer anyway."

Different problem. You're standing somewhere in a foggy landscape and you want to reach the highest point. You can't see the terrain — you can only feel the ground right under your feet. What do you do?

The obvious thing works: take a step in some direction. If it's uphill, stay. If it's downhill, step back and try another direction. Repeat until every direction is down. It's a two-line algorithm, it needs no map, and it's the honest description of most optimisation, most refactoring, and most careers. Take the current thing, perturb it a little, keep the change if it's better.

And then it stops. You reach a spot where every small change makes things worse, and by your own rule you are done. Except you're not on the mountain. You're on top of a hill — some perfectly nice bump that happens to be the tallest thing within one step of you, with the real summit sitting invisible behind the fog, higher, and unreachable because getting there means walking downhill first.

That's a local optimum, and the algorithm can't tell it from the global one. It has no idea. From the inside, a local maximum feels exactly like success: everything you try makes it worse, so you must be at the top.

Every fix for the local-optimum trap is the same fix wearing different clothes: put some randomness in. They differ only in how gracefully they do it.

• Random restarts. Climb to the top of your hill. Write down the height. Then teleport to a random spot and do the whole thing again. And again. Keep the best summit you ever found. It's cheap, it's dumb, it throws away everything you learned each time — and it works well enough that it's the default in half the optimisation code running today.
• Random jumps. Don't teleport — loosen the rule. Sometimes accept a change that makes things worse. Now you can walk down out of your little valley and stumble onto the slope of something bigger. This is the Metropolis algorithm, and the counterintuitive bit is the whole point: to reliably go up, you must be willing to sometimes go down.
• Simulated annealing. Take the metallurgy literally. Blacksmiths get strong metal by heating it until the atoms rattle loose, then cooling it slowly, so the crystal structure has time to settle into a good arrangement instead of freezing into the first mess it hits. Quench it fast and you get brittle junk. So: start hot — accept almost any change, wander wildly, don't be precious about the current answer. Cool slowly — get pickier as you go. End cold — accept only improvements, and settle.

Look at that last one again, because you have already read it. Wander freely early when there's time for a discovery to pay off; get conservative late when there isn't. That is Chapter 2's explore/exploit arc exactly — the same idea, rewritten as a temperature. Optimal stopping had a threshold, bandits had a horizon, and annealing has heat. It's one shape wearing three costumes.

Below: the same landscape, three climbers. Start with plain hill climbing and watch it die on whatever hill it happens to be born on. Then let annealing run hot and watch it do something that looks, for a while, like sheer vandalism — before it cools and lands somewhere the careful climber could never reach.

Everything so far treats chance as a shortcut — a cheaper route to an answer you could, in principle, have computed. There's one setting where it isn't a shortcut at all. It's the only defence you have.

Play rock-paper-scissors with any fixed rule and you will eventually lose to anyone paying attention, because a rule is a pattern and a pattern is a tell. It doesn't matter how clever the rule is. "Always rock" loses in one round; "the elaborate seven-move cycle I invented" loses in eight. The moment your opponent models you, being predictable is the vulnerability — and any deterministic strategy is, by definition, perfectly predictable to someone who watches long enough.

Now play at random, exactly one-third each. You can't be read, because there is nothing to read. No amount of study helps your opponent, no history of your play leaks anything, and your expected result is fixed regardless of what they do. You have made yourself un-exploitable by making yourself uninteresting. The unpredictability isn't protecting the strategy — it is the strategy.

Once you see it, it's everywhere in systems work. Poker players randomise their bluffs so their bet sizes stop being a readout of their hand. Load balancers pick a random backend — or the lesser-loaded of two random backends — because any deterministic hash is a map an attacker can use to aim all the traffic at one node. Hash tables randomise their seed per process for exactly the same reason: without it, a stranger can hand you keys engineered to collide and turn your O(1) lookups into a denial-of-service. Retries back off with random jitter, because a thousand clients retrying on a tidy fixed schedule is just a thundering herd with good timekeeping. Every one of these is the same move: where a pattern would be exploitable, spend a coin flip to have no pattern at all.

Simulated annealing is one of those algorithms whose reputation vastly exceeds its source code. It is a loop with an if in it. Everything interesting lives in a single expression — math.exp(-dE / t) > random() — which says: the worse this move is, and the colder we are, the less likely I am to take it anyway. Delete that line and you have plain hill climbing, local optima and all.

Note the four things you must supply: a neighbour function (what counts as a small change), an energy function (what you're minimising), a schedule (how fast you cool), and a step budget. The algorithm knows nothing about your problem. That's why it's in everything from chip layout to travelling salesmen to protein folding.

Here's where a lesser book tells you the universe wants you to take a chance. It doesn't, and that's not what any of this says.

The value of a random move isn't luck. It's decorrelation. Your own reasoning cut the groove you're standing in — every option you can currently think of was generated by the same mind, using the same assumptions, that produced your current position. Of course they're all nearby. That's not a coincidence, it's a mechanism: you are a hill climber, and your proposal distribution is centred on where you already are. A random move is the only kind that isn't downstream of your priors. It doesn't find you a better answer — it finds you a different neighbourhood, and lets your ordinary, perfectly good climbing do the rest.

Which gives a usable rule, and it's narrower than the inspirational version. Shake things up when you've stopped improving. Not when things are working. Annealing doesn't accept a worse move because chaos is virtuous; it accepts one because it is trying to get somewhere and the local moves have run out. If you're still climbing, keep climbing — jitter costs you real altitude and buys you nothing.

And the caveat the poster version always leaves off: annealing says wander early and settle late, and it means it. A random move costs almost nothing at 25 — you have a thousand steps left to recover and the schedule says you should be hot. The same move at 55 is made near the end of the budget, when the cooling schedule is telling you, correctly, that you no longer have the runway to climb a new mountain from the bottom. That's not a counsel of despair. It's a temperature. The algorithm doesn't say never move — it says the bar for moving should rise as the clock runs down. That's not resignation; it's arithmetic.

Randomness was about one agent groping through fog. The next chapter has a lot of them, and they're all shouting at once. How do machines agree on anything when messages get lost, arrive out of order, or show up twice? How do a million clients share a wire without a conductor? It turns out the protocols we invented for computers talking to computers — exponential backoff, acknowledgements, congestion control, the awful cost of buffering — describe your inbox, your group chat, and your relationships with unsettling accuracy.