The Measure of Information

To learn is to tell apart

Let us start from an ordinary experience, one we live through every day but rarely stop to think about: what happens in our minds when we learn something new? Before we get an answer, we hold several possibilities open. When the answer arrives, some of those options close and disappear. To learn something means, in the most concrete sense, to move from a longer list of things that might be true to a shorter one. This intuition underlies every riddle, every police investigation and every medical diagnosis: we look for clues that cut away uncertainty.

In 1948, a young American mathematician and engineer named Claude Shannon took a step of brilliant simplicity: he proposed that we measure information by looking only at this narrowing of possibilities, setting aside the literary meaning, the emotional weight or the deeper truth of the message. For Shannon, the information carried by a message is precisely the amount of uncertainty it destroys — that is, how far it shortens the list of things that might have been. The message is seen simply as a choice made from a known repertoire, not as a philosophical interpretation of the world.

At first sight, the consequences of this definition may seem odd. If a message confirms something you already knew with complete certainty — that the sun will rise tomorrow morning, say — it brings you no new information at all, however vital sunrise may be to our lives. Why? Because the list of possibilities already had a single line on it and still has one; there was no doubt to dispel. A message that settles between two equally plausible options, on the other hand, brings exactly one fundamental unit of knowledge, whether it concerns the toss of a coin (heads or tails), the colour of a pair of socks picked in the dark or the result of a medical test. That unit is called the bit (a shortening of the English binary digit, which also carries the sense of “a scrap”) and it is the smallest scrap of information there can be: the answer to a single well-chosen yes-or-no question. What we measure, then, is the power to tell options apart, not the emotional weight of the news.

This view presupposes something essential: the notion of information only makes sense relative to a list of possibilities we have in view from the start. Without such a list, the question “how much information does this message bring?” hangs in the air, just as “how far did you walk?” makes no sense unless you know where you set out from. Information is not a magical property hidden inside the message itself; it is a living relation between what the message brings and what the listener did not yet know.

To see how this measure works in practice, we shall follow one clear situation from end to end: a small object is hidden in one of sixteen closed boxes, and our only instrument of search is questions that can honestly be answered with nothing but “yes” or “no”.

Linear search and binary search

Sixteen boxes sit in a neat row on the table in front of us. The object we are after may be in any of them, and we have not the slightest clue: every box has exactly the same chance of being the lucky one. We are not allowed to lift the lids ourselves. We may only put questions, and a host who knows where the secret lies will answer honestly every time, with nothing but “yes” or “no”. The natural question is this: how many questions do we need in order to find the object for certain, if we think as cleverly as we possibly can?

The first strategy that comes to mind is plain common sense, and it is called linear search. We go along the row, box by box: “Is it in the first box?”, then “Is it in the second?”, “Is it in the third?” and so on, the way we hunt for a lost key by patting one pocket after another. With great luck we hit it on the very first try. With bad luck we shall have to ask fifteen questions; and if the first fifteen answers were all “no”, we know for certain the object is in the sixteenth, without needing to ask again. The number of questions therefore depends on luck, and on average we shall need more than eight of them to reach the target.

There is a second strategy, however, far more powerful, which changes the way we frame the problem entirely. Instead of asking timidly about a single box, we ask about a whole half at once: “Is the object in the right-hand half?”. Whether the answer is “yes” or “no”, half the boxes are swept away in a single breath. We then apply the same logic to whatever group is left: from 16 boxes, 8 remain; from 8, 4; from 4, 2; and from 2, a single box, certain and found. This method is called binary search (that is, based on splitting in two). It guarantees that the object will be found in exactly four questions, wherever it may be hidden. Why exactly four? Because each question halves the number of unknowns, and 2 · 2 · 2 · 2 = 16. Four successive halvings reduce sixteen possibilities to one, without fail.

The enormous difference between the two approaches is not a matter of chance but of how the question is cut. A question of the form “Is it in this first box?” is deeply lopsided: we are almost certain to get a negative answer, and a “no” barely removes one poor possibility out of sixteen. The question “Is it in the right-hand half?”, by contrast, is perfectly balanced: whatever answer comes back, it clears away exactly half the fog. A question gives us the most information when its outcome is the least predictable, that is, when both options were equally likely. Here the role of the bit shows plainly: an answer we could easily have guessed teaches us almost nothing, whereas a genuinely uncertain answer opens our eyes.

The boxes go dark in the drawing not because anyone physically looked inside them, but because the logic of the answer ruled them out beyond appeal. Not one lid has been lifted, and yet, at the end of the four questions, we know precisely where the secret lies.

The logarithm base 2

Let us look more closely at what happens as the number of possibilities grows. With 4 questions we could tell 16 boxes apart. If we add just one more question — a fifth — our first cut can divide the world into two groups of 16 each: all at once we can settle 32 possibilities. A sixth question lets us explore 64 boxes. Every new binary question does not merely add a few more options; it doubles the total number of possibilities we can master. With only 10 questions we can find an object hidden among 1024 boxes; with 20 questions we can sift more than a million; and with 30 we pass a billion.

If we read that relation backwards, we find the instrument we need in everyday life. Given a list with some number of possibilities on it, how many successive halvings does it take to be left with just one? That number of steps has a mathematical name, the logarithm base 2 and it is written log₂. Behind a name that may sound technical, it is nothing but “the number of cuts in two” needed to reach certainty: the logarithm base 2 of 16 is 4, of 1024 is 10, and of 2 is 1. We need no heavy algebra; we need only the simple idea that the logarithm measures how many doublings or halvings connect a set of options to final certainty.

What happens if the number of options is not a perfect power of two? If we have a thousand possibilities, say, the theoretical number of halvings is about 9.97. That means 9 questions are not enough to be sure in every case, but 10 are more than sufficient. The measure of information need not be a whole number: it expresses how much freedom of choice the initial list contained, and the questions we actually put are that measure rounded up to the next step.

Now we can state the conclusion plainly: to learn which option is true out of a number of equally likely possibilities is to receive an amount of information equal to the number of halvings needed to sift them. For sixteen boxes we need four bits. A message that unerringly picks one option out of a million brings roughly twenty bits of information — exactly as much as fits into twenty clean “yes” or “no” answers. The number of questions grows astonishingly slowly while the number of options explodes; that is precisely why we can find any word in a thousand-page dictionary by opening it in the middle a handful of times.

The binary code

One essential connection remains to be made — the bridge to the world of modern computers. The string of answers we gathered along the binary search is not thrown away: letter by letter, it is the unique address of the box we found. If we write each “yes” as the digit 1 and each “no” as the digit 0, in the exact order they arrived, we get a sequence of four digits, such as 1011. That sequence works like a set of directions at a crossroads and leads unfailingly to a single box. Every box has its own distinct string, because at each step a new cut separates the remaining options into two camps.

To express something in binary is simply to identify it by the history of the choices that tell it apart from every other option on the list. This binary code does not try to describe the inner properties of the object — it does not tell us what it is made of or how much it weighs — only where it stands in relation to its neighbours. It is a clean postal address, not a painting. That is exactly why any repertoire in the world, from the letters of the alphabet and the sounds of a violin to the colours of a photograph, can be faithfully transcribed using only these two elementary symbols: 0 and 1.

When we set eight such bits side by side, we obtain a byte (known in English also as a byte). Eight bits can tell 2⁸ = 256 different possibilities apart: room enough to hold every upper- and lower-case letter of an alphabet, the digits from 0 to 9, the punctuation marks and the special characters of an ordinary keyboard. A computer does not “see” letters, warm shades of yellow or musical chords; it handles nothing but long strings of 0s and 1s, that is, answers to successive questions. What those bits mean depends entirely on the convention we agreed on beforehand: the sequence 01000001 stands for the capital letter “A” if we are reading text, for the number 65 if we are doing arithmetic, or for a particular shade of grey if we are processing a digital image.

Unequal probabilities

Up to this point we have assumed that all the boxes have strictly equal chances of holding the object, which is why cutting exactly at the middle of the list was the wisest move. But what happens when the possibilities before us are not equally likely? Think, for instance, of the letters of a natural language.

Writing a message on a computer means transmitting a succession of letters, each chosen from a shared repertoire. If we have a simplified alphabet of thirty-two characters and treat them all as equally likely, every letter costs us exactly 5 questions — that is, 5 bits — and a text of a thousand characters will ask five thousand bits of memory.

We know perfectly well, though, that letters do not occur with the same frequency. In English, vowels such as “e”, “a” or “i” turn up in nearly every word, while letters such as “q”, “x” or “z” appear only now and then. If we always cut the list mechanically down the middle, both kinds get codes of the same length: 5 bits for a letter that is everywhere and 5 bits for a rarity. That is an obvious waste of space and effort. To see how we might put things right, we return to the game of boxes, but this time we let the cut move freely.

The dividing line is not obliged to sit fixed at the middle of the count of boxes. By moving the slider we create codes of unequal length: a favoured box can be identified by a single bit, while others will ask for several. As long as all boxes have equal chances, moving the line is a clear loss: the lopsided question almost always gets a predictable answer, and the average number of questions goes up.

When the probabilities differ, however, that very lopsidedness becomes the saving key. The ideal cut is not the one that splits the raw number of options in two, but the one that splits the total probability in two: on one side we put the frequent options which, added together, gather 50% of the chances, and on the other side the rest. Done that way, every answer stays as unpredictable as an honest coin toss and brings us a whole bit of clarity. Frequent symbols get short, economical codes, and rare symbols get longer ones. Overall, the average length of the text drops appreciably below 5 bits per character, without losing so much as a single letter. This is exactly the brilliant intuition Samuel Morse had in the middle of the nineteenth century: for the commonest letter of the English alphabet, “E”, he chose the shortest signal there could be — a single short dot — leaving the long combinations for the letters that are rarely used.

The minimum theoretical limit of that average length, for a given set of probabilities, bears a famous name in science: entropy. That is the fascinating subject we shall open in the next lesson.

What this measure assumes

Before we travel further, it is worth taking a step back and looking clearly at the foundations this theory rests on, for everything we learn later — right up to the most advanced models of artificial intelligence — has its roots here.

• A clear list of possibilities, agreed in advance by sender and receiver. The notion of information is always relative to that initial state of knowledge: the same message brings four bits of novelty to someone hesitating between sixteen options, but zero bits to someone who already knew the answer.
• Probabilities and degrees of expectation. The measure of information does not enquire into what is moral, beautiful or useful, but into how unexpected an event is. We measure the degree of objective surprise a piece of news causes, not its philosophical rightness.
• A complete detachment from subjective meaning. A false message or a well-turned fable carries exactly as many bits as a rigorous scientific truth, if both choose with the same precision from the repertoire of signs. This neutrality is not a defect; it is the very secret of the theory’s universal reach: precisely because it does not depend on human interpretation, the measure of the bit works just as faultlessly for the letters of a book, the pixels of a photograph taken from space, the genetic sequences of DNA or the billions of parameters in a modern neural network.

In exchange for that abstraction we gain a formidable advantage: a universal measure that can be added, compared, stored and optimised. Thanks to it we can calculate precisely how much room a text takes up in memory, how far a photograph can be compressed without visible loss, how many bits can travel each second through an optical fibre and — as we shall see in the second half of this course — how well an intelligent machine has learned to anticipate the next word in a conversation.