How much is a surprise worth?

The basic unit of uncertainty is one choice between two equally likely answers: heads or tails, yes or no. Shannon measured information by how many such even choices it takes to settle a question. The unit is the bit, short for binary digit, a word he credited to the statistician John Tukey.

One toss of a fair coin carries one bit, because telling someone how it landed settles exactly one even choice. Two tosses carry two bits, since four outcomes are now equally likely: heads-heads, heads-tails, tails-heads and tails-tails. Each extra toss doubles the number of possible outcomes and adds one more bit. A switch that is either on or off can store one bit, and a computer's memory is built from billions of such switches.

In the game Twenty Questions, one player thinks of something and the other may ask only yes-or-no questions. The best questions split the remaining options in half. Is it alive? Is it bigger than a loaf of bread? When both answers are equally likely, each reply settles one bit.

Halving adds up quickly. Suppose a friend picks one of eight cards. Ask whether it is among the first four, then which pair, then which card: three questions, so the choice was worth three bits. Every extra question doubles the number of options you can handle, so twenty questions can single out one item among about a million, which is two multiplied by itself twenty times. A choice among equally likely options holds as many bits as the halvings needed to reach the answer.

Not every answer is a fair coin toss. If a friend who is always late turns up late, you learn little; if they turn up early, you learn a lot. Shannon's measure matches that feeling. The less likely an event, the more information its happening carries, an amount often called its surprise, or surprisal.

Surprise is counted in the same bits. An event with a one-in-two chance carries one bit when it happens, and a one-in-four event carries two bits. A one-in-eight event carries three bits, and a one-in-sixteen event carries four bits. Each halving of the chance adds one more bit, so a one-in-a-thousand event carries almost ten. Something certain carries no bits at all. That is why news that the sun rose today tells you nothing: it was certain to happen, and a snowfall in the Sahara, being rare, tells you a great deal.

A single event has a surprise. A whole source of events, such as a coin tossed again and again or letters arriving down a telegraph wire, has an average surprise: each outcome's surprise, weighted by how often that outcome turns up. Shannon called this average entropy. It measures how unpredictable the source is, in bits per event.

A fair coin has an entropy of one bit per toss, since heads and tails each carry one bit and each turns up half the time. Now load the coin so that heads comes up 90 times in 100. Heads is hardly news, about 0.15 bits, while tails is a jolt of more than three bits that rarely comes. Weighted by how often each happens, the average is under half a bit. The loaded coin is easier to predict, so each toss tells you less.

Plot a coin's entropy against its chance of landing heads and you get a hill. A two-headed coin, certain to land heads, sits at zero at one edge, because every toss is known in advance. As the odds even out the entropy climbs, and it peaks at exactly one bit for a fair coin, whose heads and tails are equally likely.

This holds for any source, not just coins. With a fixed number of possible outcomes, entropy is greatest when all of them are equally likely, because then no guess is better than any other. For eight equally likely cards it is three bits, just as the halving game found. Any tilt in the odds, any pattern that makes some outcomes likelier than others, lowers the entropy and hands a clever guesser something to work with.

Shannon borrowed the word from physics. His formula for average surprise matches, in form, a formula physicists had used since the late nineteenth century for entropy in heat and gases, the quantity that grows as perfume spreads through a room. A popular story, told by the engineer Myron Tribus, has the mathematician John von Neumann advising Shannon to use the name because nobody really knows what entropy is, so in a debate he would always have the advantage. Asked about it in 1982, Shannon doubted the story and said the word came from thermodynamics.

The kinship is real but is not identity. A physicist's entropy grows with the number of arrangements of molecules that look the same from outside, so it tracks how much the outside view leaves unknown. Shannon's measures the unknown in any set of chances, of letters, coins or anything else.

How much information does a letter of English carry? If all 26 letters were equally likely, each would carry about 4.7 bits, the entropy of 26 even choices. Real English is lopsided. E makes up about one letter in eight, while Q and Z turn up less than once in a thousand letters. Taking these uneven letter frequencies into account brings the average down to about 4.1 bits per letter.

The same unevenness is what the ninth-century Baghdad scholar al-Kindī used to read ciphers without their key. A cipher that swaps each letter for a symbol keeps every letter's count, so the commonest symbol still points to the commonest letter. Shannon, who worked on secret codes during the Second World War, saw the fact from the other side: some letters being far more common than others makes a text predictable, and a predictable text carries fewer bits per letter.

In 1951 Shannon measured English more directly, using people as the predictors. He showed a reader a passage one letter at a time and asked them to guess each next letter before it was revealed. In one short sample his subject got about seven letters in ten right on the very first guess.

A letter you could have guessed tells you little. From tests like these, Shannon estimated that ordinary English carries only about one bit per letter once the reader knows the hundred letters before it, somewhere between 0.6 and 1.3. An alphabet of equally likely letters would carry 4.7. The gap is redundancy: the share of a text that its language already fixes, which Shannon put at roughly 75 per cent. It is why you can often read a message with many of its letters missing.

Redundancy can be put to work, and the telegraph showed how a century before Shannon. In Morse code, each letter is sent as a pattern of short dots and long dashes. Samuel Morse's partner Alfred Vail is said to have counted the metal type in a newspaper's printing office in Morristown, New Jersey, to learn which letters printers used most, and the commonest letters got the shortest signals. E became a single dot and T a single dash, while rare letters such as Q and Z need four signals each.

This is variable-length coding: short codes for frequent symbols and long ones for rare symbols. A single message may not gain, but on average, across many messages, the saving is large, because the short codes are the ones sent over and over.

A zip file uses the same principle as Morse code, with modern refinements. It finds the patterns in a file, such as repeated words and uneven letter counts, and rewrites the file with short codes for whatever is common. One of its main tools, Huffman coding, was published by the student David Huffman in 1952. This is lossless compression: unzipping gives back every bit of the original exactly.

Shannon's theory sets the limit. On average, no lossless code can use fewer bits per symbol than the source's entropy. Redundant English shrinks a lot, because much of it could have been predicted. A file of fair coin tosses is different: it has no pattern to exploit. Each toss already carries a full bit and is genuine news, so on average the file cannot be shrunk at all.

Morse and Huffman codes use fixed counts of how common each symbol is. A code does better still if it predicts each symbol from everything that came before. After "the Prime Minister of", a good predictor expects a country's name, and a well-built code can spend about as many bits on each symbol as that symbol's surprise: very few on a likely one, more on a rare one. Sender and receiver run the same predictor, so the receiver can decode.

Here the threads meet. The better a model predicts, the fewer bits its code needs, so predicting well and compressing well are one skill. In 2023 researchers at DeepMind tested this with a large language model. Leaving aside the model's own size, it squeezed Wikipedia text to about 8 per cent of its size, against 32 per cent for gzip, a standard zip-style tool.

A language model, the software inside chat assistants, is first trained on one task. Given the text so far, it gives every possible next token, a word or piece of a word, a probability. Then the real next token is revealed, and the model is scored by its surprise at it. Had it given that token a one-in-two chance, the surprise is one bit; one in a thousand, about ten bits.

Averaged over billions of tokens, this score is called cross-entropy, and training nudges the model's settings to push it down. It measures the real text's surprise as seen through the model's guesses, so it can never fall below the text's own entropy. Whatever in the text is truly unpredictable stays surprising however good the model gets. The gap above that floor is the model's room to improve.

Why should so narrow a task teach so much? Because lowering its surprise on varied text rewards capturing every regularity the text holds. To be unsurprised by what follows "she poured the milk into her", a model needs grammar and some sense of kitchens. To be unsurprised by what follows "the capital of Kenya is", it needs a fact. Arithmetic, computer code and the plot of a story all make some next tokens likelier than others.

Grammar, facts and habits of reasoning all make text more predictable, so a model that keeps lowering its cross-entropy is pushed to pick them up wherever they leave traces in writing, and a remarkable amount of what people know does. The limit is the text itself. A model learns the patterns in what was written, not whether it was true, so a low surprise score is no guarantee that its answers are accurate.