Surprise and entropy

Pick a letter at random from an English page. If the letter is z, you have learned 10.4 bits. If it is e, you have learned 3.5 bits [S:36:44]. Same alphabet, same page, different amounts of news.

That gap answers this section's question, how much information is in one symbol. The amount depends on the probability of the symbol, not on its shape. A rare letter is a larger surprise, and the surprise is the information. This chapter asks how short a message can be; the surprise of one symbol is the unit in which message length is measured. !Information content against probability. The curve is log${}_2(1/p)$, so the coin's common outcome at 0.9 carries 0.152 bits and its rare outcome at 0.1 carries 3.322 bits, while a fair coin's outcome at 0.5 carries 1 bit. The curve falls steeply as p approaches zero and gently as p approaches one: a rare symbol is expensive news, a likely one is cheap. The amount belongs to the probability, not to the shape of the symbol. Status: re-simulated.

Surprise as a number. The information content of an outcome is its surprise, measured in bits, where one bit is the surprise delivered by a fair coin flip. Write p(x) for the probability of the symbol x. The information content is the base-two logarithm of one over that probability, so the answer comes out in bits. A symbol with probability one half carries one bit, and a symbol with probability one quarter carries two.

$$\text{information content of }x={\log }_2\frac{1}{p(x)}$$

The equation says that a likely outcome carries little information and a rare one carries a lot. It also says that no outcome can carry a negative amount, because a probability is never above one. The scale is worth fixing in your head: one bit is one yes-or-no question, about 10 bits is one outcome out of a thousand, and about 20 bits is one out of a million.

Why a logarithm. Two independent fair coins carry two bits together, not one, because independent news should add and a logarithm turns the multiplication of probabilities into addition [S:36:80]. Additivity alone leaves the constant free, because $c{\log }_2(1/p)$ satisfies it for every c. Shannon's three requirements force the form with a positive constant [S:156:11]: continuity in the probabilities, a rise with n when n outcomes are equally likely, and the grouping rule for a split choice. The fair coin fixes that constant at one; another base changes the numbers by a constant factor, but the comparisons survive.

Average over a source. A source sends many symbols, each with its own probability. Its entropy is the average information content, with each symbol weighted by how often it appears. For a random symbol U, the entropy H(U) is a sum over all possible symbols.

$$H(U)=\sum _{u}p(u){\log }_2\frac{1}{p(u)}$$

The equation says that entropy is a weighted average of surprise, not the surprise of one particular message. A source that always sends e has entropy zero, because nothing ever surprises you. A source with many equally likely symbols has high entropy.

The entropy is largest when the outcomes are equally likely, and its value is then the logarithm of the number of outcomes [S:75:467]. A fair coin has two outcomes, so its entropy is 1 bit. A source with four equally likely symbols has 2 bits, and one with eight has 3. The uniform source is the hardest to guess and the hardest to compress.

Worked example. A coin lands heads with probability 0.9. Heads carries ${\log }_2(1/0.9)=0.152$ bits. Tails carries ${\log }_2(1/0.1)=3.322$ bits. Weight by the probabilities: $0.9\times 0.152+0.1\times 3.322=0.469$ bits.

A fair coin has entropy 1 bit. The 0.9 coin sits near the bottom, because you can guess it most of the time.

Push the bias further and the entropy keeps falling. At probability 0.99 for heads, the entropy is 0.081 bits. At probability 0.5 it is 1 bit. The curve is flat near the fair coin and drops steeply near the loaded ends, so a small bias costs little and a large one costs a lot.

A single message can carry more or less than the entropy. Entropy is the long-run average over many messages from the same source, so it describes the source rather than one lucky or unlucky outcome. The distinction between the average and the individual message is the distinction between a property of the source and a property of one transmission, and keeping it straight prevents most of the confusion that this subject produces.

The less probable an outcome is, the greater its information content [S:36:79]. Flattening the distribution therefore raises the average. A loaded coin is considerably easier to compress than a fair one, because its typical output is easier to guess.

Entropy has a price. It is an average over a distribution you must know in advance, so wrong probabilities give a wrong number [S:36:110]. It also treats symbols as independent draws, and real data has correlations that a single-symbol entropy cannot see [S:36:150]. And it measures surprise, not usefulness: a message that is perfectly predictable can still be the one you need.

Both limits matter in practice, because a model that is right about the source is worth more than a clever code built on the wrong probabilities. The next section adds the tools for pairs of symbols.

The formal statement. An ensemble is a finite alphabet with probabilities that are positive and sum to one [S:36:34]. Its entropy is

$$H(p)=\sum _{a}p(a){\log }_2\frac{1}{p(a)}.$$

The equation says that you weight each symbol's surprise by the chance of seeing it, then add. Shannon derives this form from three requirements [S:156:11]. The function is continuous in the probabilities. When n outcomes are equally likely, it increases with n. If an outcome of probability $p_{n-1}+p_n$ is split into outcomes of probabilities $p_{n-1}$ and $p_n$, then $H(p_1,\dots ,p_n)=H(p_1,\dots ,p_{n-1}+p_n)+(p_{n-1}+p_n)H\left(\frac{p_{n-1}}{p_{n-1}+p_n},\frac{p_n}{p_{n-1}+p_n}\right)$, so the split raises the entropy by the weighted entropy of the two new parts [S:156:10]. Those three hypotheses force the logarithmic form, and the choice of constant fixes the unit. This layer omits the algebra of Shannon's Appendix 2, because the three statements already carry the idea.

The derivation you can check. Start from independence. If x and y are independent, their joint probability is the product, so

$${\log }_2\frac{1}{p(x,y)}={\log }_2\frac{1}{p(x)}+{\log }_2\frac{1}{p(y)}.$$

The equation says that independent surprises add. A measurable function of probability with that property is $c{\log }_2(1/p)$ for some constant c, so additivity fixes the shape up to that constant [S:36:80]. The constant, and with it the unit, needs one more condition: Shannon's monotonicity and grouping axioms, or the convention that a fair coin carries one bit [S:156:11]. This argument is shorter than Shannon's and weaker: it assumes the surprise depends on the probability alone, which is the part his axioms prove.

The edge case. Apply the formula to a continuous variable and the claim that information is never negative fails. Differential entropy can be negative, because a density may exceed one; a uniform density on an interval shorter than one unit gives a negative value [S:62:270]. The discrete formula keeps its sign because a probability is at most one. L1's sentence that no outcome carries a negative amount is true for symbols and false for densities.

What L1 hid, and why that was safe. L1 fixed the base at two and called the unit a fair coin. That is a convention, not a theorem: another base multiplies every entropy by a constant, so every comparison in the chapter survives. L1 also treated the probabilities as known. The definition needs them, and estimating them from data is a separate problem with its own bias [S:34:163]. The simplification was safe because the section asked what one symbol carries when the source is given.

Where the analogy breaks. The sentence "one bit is one yes-or-no question" holds only for a question that splits the remaining probability in half. A badly chosen question can leave the uncertainty almost unchanged, and a single answer can remove more than one bit when it surprises you. The expected number of yes/no questions is at least the entropy, with equality only when every question splits the remaining probability in half, which requires each $p_i$ to be a power of $1/2$ [S:36:110] [S:36:115]. The analogy describes the best case, not every case.

Original sources. Shannon defines the entropy of a set of probabilities and proves that three requirements single it out [S:156:11]. The same paper introduces the bit and treats English as a source whose redundancy can be measured [S:156:15]. MacKay's Chapter 4 turns the definition into the coding argument this chapter uses and works the monogram entropy of English as an example [S:36:44].

An open question. Nobody knows the entropy rate of English. Shannon lists three routes: compute the entropy of successive approximations to English, delete letters and ask readers to restore them, or use results from cryptography [S:156:15]. Each route gives a bound, and every bound here has the same direction: a model that assigns probability q to the text has cross-entropy $H+D_{\mathrm{KL}}(p\Vert q)$ at least H, so a better compressor and a better predictor both lower an upper bound on the rate [S:36:110]. Shannon's deletion test points the same way: if half the letters can be restored, the redundancy must exceed one half, so the entropy is below half the maximum [S:156:15]. A lower bound needs a separate counting argument, and the crossword construction supplies one [S:36:272]. MacKay repeats the estimate of about one bit per character and attributes it to Shannon without claiming exactness [S:36:113]. A sequence of models whose measured cross-entropy converges from above would approach the rate from above; it would not meet a lower bound.

A frontier result. A language model trains by minimising cross-entropy, and cross-entropy equals entropy plus the KL divergence from the true source to the model [S:62:271]. That identity makes compression a training objective. A model that predicts text better also compresses it better, and the remaining gap is the divergence it has not removed. Perplexity is $2^{H_{\mathrm{ce}}}$, and $H(p^{\ast })\le H_{\mathrm{ce}}(p^{\ast },p)$, so the perplexity is at least $2^H$; its base-two logarithm is the upper bound on the entropy rate, not a measurement of it [S:62:272].

Why the rate is hard. A bound from a compressor depends on the model class, and a bound from a reader depends on the reader's background. Neither is a property of English alone, so the two kinds of bound answer slightly different questions.

What to read next. Read Shannon's Part I for the axioms and the English discussion [S:156:11]. Read MacKay 4.1 to 4.4 for the coding proof and the typical set [S:36:79]. Read Murphy 5.2 for cross-entropy, perplexity and the warning about differential entropy [S:62:270]. Keep the last two together: one gives the definition, and the other shows what changes when you estimate it from text.