A die, and only a coin
TAY: We need a die and there isn’t one. I have a coin.
NOOR: A fair one?
TAY: Fair as anything. So flip me a number, one through six.
NOOR: A coin gives me heads or tails. You want one of six things. Those don’t divide.
TAY: Flip it a few times, then. Three flips is eight outcomes, and eight covers six with room to spare. Read the three flips as a little binary number, throw away the two you don’t need.
NOOR: And when the three flips come up as one of the two I don’t need?
TAY: Then you flip again. It won’t happen often.
NOOR: It happens a quarter of the time. Two spare outcomes out of eight. So sometimes three flips, sometimes six, sometimes nine. I’m going to keep score of the flips, if you don’t mind. I want to know what this die is costing us.
They play a while. Noor keeps a running tally in the margin.
NOOR: Four.
TAY: Four what?
NOOR: Four flips a roll, on the average. You pay three every time, and then a quarter of the time the reject sends you back for three more, and a quarter of those go back again, and if you add up that whole shrinking tail it settles at four. Three flips of honest work and one flip of waste.
TAY: Waste is a strong word for a rule that works.
NOOR: Look at what we throw away, though. When the three flips read as a reject, I don’t erase all three. The last one was still a clean coin flip. Heads or tails, fair, untouched by the reason we’re rejecting. If I keep that bit and carry it into the next attempt, the next attempt only needs two fresh flips, not three.
TAY: Does that actually save anything, or does it just feel tidy?
NOOR: It moves the average from four down to eleven-thirds. Three and two-thirds. A third of a flip a roll, saved by refusing to bin something that was never spoiled.
TAY: A third of a flip is nothing.
NOOR: A third of a flip is nothing until you roll a billion times, and then it’s three hundred million flips you didn’t have to make. But leave the billion aside. I want you to see where eleven-thirds sits, because it isn’t an accident.
TAY: Where does it sit?
NOOR: There’s a number under the die. For a fair six it’s a hair under two and three-fifths. Two point five eight five, near enough. No scheme, no cleverness, nothing you or I or anyone will ever invent, can roll a fair six-sided die for fewer than that many fair flips on average. Eleven-thirds is above it. We’re paying about one extra flip over the floor, and that extra is the price of insisting the die come out exactly fair.
TAY: Why two point five eight-something? Why not three, one for each doubling up to six?
NOOR: Because you aren’t buying faces. You’re buying surprise. When the die lands, how surprised should you be? On a fair six, exactly as surprised as two point five eight-something coin flips would make you. That quantity has a name and it’s the entropy, and it’s the real thing you’re purchasing every roll. The coin is your currency. Each flip mints one bit of surprise, no more, and you can’t buy two-point-five-eight bits of it for two flips. The floor is just the honest exchange rate.
TAY: Then a loaded die should be cheap. Say a die that lands six almost every time. Barely a surprise at all. Should cost me almost nothing.
NOOR: Say it lands six fifteen times in sixteen. Its surprise, its entropy, is about a third of a bit. Tiny. So roll it once and tell me what you’d expect to pay.
TAY: A third of a flip. Maybe one, to be safe.
NOOR: One roll of that loaded die costs almost two flips.
TAY: Two? For the thing that’s barely a surprise?
NOOR: For one roll, yes, and this is the part that catches everyone. To honor that one-in-sixteen face you still have to resolve down to a sixteenth of the number line, and resolving to a sixteenth takes flips whether or not the rare thing shows up. The surprise is small. The bookkeeping to place a single outcome exactly is not. The floor promises you the surprise plus less than two, and for a lopsided die that “less than two” is nearly the whole bill.
TAY: So the loaded die is a bad deal. Fine.
NOOR: For one roll. Now roll it a thousand times and don’t reset between rolls. Carry the leftover, the way we carried that rejected bit, from each roll into the next. The bookkeeping cost, the part that was nearly the whole bill, doesn’t repeat. It was a fixed toll, paid once, spread across every roll after. A thousand rolls of the loaded die cost about a thousand times its tiny entropy, plus that one small toll amortized into vapor. Per roll, you drift right down to a third of a bit. The floor was telling the truth all along; you just have to stop paying the toll a thousand separate times.
TAY: So it is cheap.
NOOR: In bulk. A single draw costs its surprise plus a fixed toll of under two flips. Draw a lot and the toll vanishes and you pay only the surprise. That toll, the “under two,” is the whole of the recent work on this. Someone worked out how to carry the leftover forward with almost no memory, so the toll shrinks to nearly nothing without you having to hoard the entire history of the game.
TAY: Back up. You keep saying surprise, not faces. But six faces cost more than two, surely. More things, more flips.
NOOR: Watch. A fair coin, two faces, costs one flip. A loaded coin, still two faces, can cost close to two. Same two faces, double the price. Now here’s an eight-faced die, peaked so its odds halve down the row, a half then a quarter then an eighth and on to the tail. Eight faces. It costs a hair under two flips a roll, and I mean that exactly, not in bulk. A plain fair four-sided die costs two. Eight faces, cheaper than four. Count the faces all you like; the count won’t tell you the price. The surprise will, every time.
TAY: All right. One more. This coin I’ve been flipping, I’ll be honest, I think it’s bent. Lands heads more than tails. Is our whole game ruined?
NOOR: How bent? What’s the bias?
TAY: No idea. That’s the trouble. I can’t measure it here.
NOOR: You don’t need to. Flip it twice and look at the pair. Two heads, throw the pair out. Two tails, throw it out. But heads-then-tails, call that a one, and tails-then-heads, call that a zero. Those two mixed pairs, whatever your bent coin’s bias is, happen equally often, because each is one head and one tail in some order and the coin doesn’t care about order. So the one and the zero come out exactly even. A fair bit, pulled from a coin neither of us can measure.
TAY: The bias just… doesn’t matter?
NOOR: It divides straight out. Any bias in the whole open range, and the trick doesn’t flinch. That’s the same law we’ve been paying all night, only running backwards. Forwards, you spend fair flips to buy a crooked die and the surprise sets the price. Backwards, you spend crooked flips to buy a fair bit, and the same surprise sets what you can get. You cannot pull more fair bits out of that coin than the surprise it carries. Von Neumann’s little sort is honest but it’s a spendthrift. It throws away most of the coin. There are tighter ways that squeeze it down to the surprise and no lower. Neither direction lets you cheat the exchange rate.
TAY: So the coin was never really about heads and tails.
NOOR: The die was never about faces, and the coin was never about heads. Both were only ever about how much you didn’t know before it landed. Pay in surprise. Collect in surprise. The faces are the story we tell over the top of the arithmetic, and the arithmetic doesn’t count faces. It counts the dark before the answer.
Tay flips the bent coin twice. Heads, then tails. Noor writes down a one.
