Math paradoxes

Glossary / Entropy

Glossary · entropy and the bit

Which coin tells you more: a fair one, or one that almost always lands heads?

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 wordspictures, analogies, small numbers

“In plain words” is hidden on all puzzles.

Two coins

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?

Guess the number and count the bits

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.

Questions0
Bits gained0
Numbers left100

    A bit is one fair yes-or-no answer

    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.

    Rigoroustables, charts, formulas

    “Rigorous” is hidden on all puzzles.

    The entropy curve of a coin

    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.

    Bits per toss–
    Surprise: heads / tails–
    Tosses per bit–

    The formula: average surprise

    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 learnOptionsEntropy, bits
    A fair coin21
    A die62.58
    A card from a deck525.70
    A number from 1 to 1001006.64
    One person among 8 billion8 billion32.9

    The last row means that anyone on Earth can be found with 33 good yes-or-no questions.

    The rare surprises a lot, but rarely

    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.

    Where bits get counted

    • A good question splits in halfLooking for the change that broke a website: test the middle of the range, not the latest change. The same goes for surveys: a question everyone answers "yes" teaches you nothing.
    • Password strength8 random lowercase letters give 37.6 bits. 4 random words from the 7,776-word Diceware list give 51.7 bits and are easier to remember. Only randomness counts: "Password1" has almost zero bits, because it is guessed first.
    • Text compressionFor 26 letters and a space, log2 27 ≈ 4.75 bits per character. But the next letter is often guessable. In 1951 Shannon had people guess text letter by letter and put the entropy of English at 0.6–1.3 bits per letter. That is why archivers shrink text several times over.
    • Decision trees and WordleMachine learning algorithms pick the feature that lowers the entropy of the answer the most: this is called information gain. The best first word in Wordle is found the same way: the one whose clues split the possible words most evenly.
    Deepergeneralisations, theory, history

    “Deeper” is hidden on all puzzles.

    Fewer questions than log2 n

    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.

    WeatherChanceQuestionsSurprise, bits
    Sunny1/211
    Cloudy1/422
    Rain1/833
    Snow1/833

    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.

    Where the words "bit" and "entropy" come from

    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.

    Where it shows up

    More on “Probability”

    All terms →