Glossary / Entropy
Both coins can land either way, and every toss answers the same question: heads or tails. It seems they should tell you the same amount. But with the lopsided coin you bet on heads in advance and are almost never wrong, so the toss tells you very little. Entropy measures exactly this: how much you didn't know before the answer. The bit is its unit: one answer, yes or no, when both are equally likely.
“In plain words” is hidden on all puzzles.
Coin A is fair: heads and tails 50% each. Coin B is bent and lands heads 99 times out of 100. A friend tosses a coin in the next room and shouts the result to you.
How many tosses of coin B tell you as much as a single toss of coin A?
About 12: one toss of coin B carries only 0.08 bits.
Information is not the number of possible answers but how much the answer surprised you. A fair coin leaves you completely in the dark every time: you can't guess, and each result is real news. With coin B you say "heads" before the toss and you're right 99 times out of 100. A rare tails is big news, but it comes once in a hundred tosses, so on average coin B tells you almost nothing.
The computer has picked a whole number from 1 to 100. Ask two kinds of questions: "is it more than X?" or "is it X?". The slider or a click on a cell picks X. Before you ask, see how many bits the question will give on average: the closer yes and no are to fifty-fifty, the more. Try asking at random first, then try halving.
A question where yes and no are equally likely throws away exactly half the options. That is 1 bit. Two such questions leave a quarter, three leave an eighth. So 20 good questions pick one option out of 220 = 1,048,576, a million. That is the power of the game "Twenty Questions": you can think of almost anything.
The question "is it 37?" also has two answers, but you almost always hear "no", and that "no" throws away just one number out of a hundred. It gives the same 0.08 bits as coin B. Entropy is how many bits an answer carries on average or, equivalently, how many fair yes-or-no questions it takes on average to learn it. For 100 equally likely numbers it is 6.64 bits, so halving never needs more than 7 questions.
“Rigorous” is hidden on all puzzles.
Move the slider: it is the chance of heads. The curve shows how many bits one toss carries. It peaks in the middle, at the fair coin, and drops to zero at both ends: a coin that always lands heads tells you nothing. Then toss the coin 100,000 times and compare the average surprise with the formula.
An event with probability p, when it happens, brings −log2 p bits. The rarer the event, the bigger the surprise: an outcome with chance 1/2 gives 1 bit, one with chance 1/8 gives 3 bits. Entropy is the surprise averaged over all outcomes, weighted by their probabilities:
H = −Σ pi · log2 pi
For coin B: 0.99 · 0.0145 + 0.01 · 6.64 ≈ 0.08 bits. Tails surprises you by 6.64 bits, exactly as much as guessing a number from 1 to 100 at the first try, but it is so rare that it barely counts on average. If n options are equally likely, the formula is simply H = log2 n, the largest entropy n options can have.
| What we learn | Options | Entropy, bits |
|---|---|---|
| A fair coin | 2 | 1 |
| A die | 6 | 2.58 |
| A card from a deck | 52 | 5.70 |
| A number from 1 to 100 | 100 | 6.64 |
| One person among 8 billion | 8 billion | 32.9 |
The last row means that anyone on Earth can be found with 33 good yes-or-no questions.
The chance of matching all 6 numbers in a 6-out-of-49 lottery is 1 in 13,983,816. The message "you won" carries 23.7 bits, as much as 24 fair coin tosses. "You lost" carries about 0.0000001 bits: you knew it anyway. That is why news is what nobody expected. A forecast of "dry in the Sahara tomorrow" tells you almost nothing, even though it is always right.
“Deeper” is hidden on all puzzles.
Weather comes in four kinds, so it seems to take 2 questions: log2 4 = 2. But if it is sunny half the days, cloudy a quarter, rain and snow 1/8 each, it pays to ask in turn: "sunny?", then "cloudy?", then "rain?". A sunny day takes one question, a cloudy one two, the rest three. On average that is 1.75 questions, which is exactly the entropy of this weather.
| Weather | Chance | Questions | Surprise, bits |
|---|---|---|---|
| Sunny | 1/2 | 1 | 1 |
| Cloudy | 1/4 | 2 | 2 |
| Rain | 1/8 | 3 | 3 |
| Snow | 1/8 | 3 | 3 |
Shannon proved that on average you can never do with fewer questions than the entropy, and that you can always get close to it. Morse code works on the same principle: E, the most frequent English letter, got the shortest sign, a single dot. In 1952 David Huffman showed how to build the shortest such code for any frequencies, and his method still runs inside ZIP, JPEG and MP3.
Claude Shannon of Bell Labs published "A Mathematical Theory of Communication" in 1948. There the bit first became the unit of information, and Shannon credited the word itself, short for binary digit, to his colleague John Tukey. He took the name "entropy" from physics, because the formula matches the entropy of Boltzmann and Gibbs. According to Myron Tribus (Scientific American, 1971), the name was suggested by John von Neumann: nobody really knows what entropy is, so in a debate you will always have the advantage. Whether it really happened that way is uncertain, but the story stuck.
Counting how many ways things can be ordered or chosen: permutations n!, combinations C(n, k).
A well-shuffled deck is almost certainly in an order nobody has ever seen.
The chance of an event given that something else is already known.
Almost all NBA players are tall, but almost all tall people are not NBA players.
Events are independent if knowing about one doesn't change the chances of the other.
After five heads in a row tails is no more likely: the coin remembers nothing.
The rule for updating confidence when new evidence arrives: prior odds × strength of the evidence.
Two weak pieces of evidence together can be strong, while one striking piece means little if the claim was unlikely.
How many successes you get in n independent tries when each has the same chance p.
Toss a coin 100 times: exactly 50 heads is the most likely result, yet it comes up only 8 times in 100.