Bits & Surprise

1 Information is surprise

A weather report for a desert town almost always says sunny, and occasionally says rain. A report of sun tells you very little, because sun is what you expected. A report of rain tells you much more. Both messages arrive in the same format from the same source; they differ only in the probability of the event they describe. Shannon defined the information in a message so that it depends on exactly this probability:

$p(x)$ is the probability of the event, between 0 and 1. The minus sign makes the result positive: the $\log$ of a number $\le 1$ is $\le 0$. Base 2 sets the unit to bits: a message reporting an event half as likely carries one more bit.

The formula is built from the logarithm logarithms ↗, which counts repeated doublings: $\log_2 8 = 3$ because doubling 1 three times reaches 8. In the same way, $-\log_2 p$ counts halvings below certainty: an event with $p = \tfrac12$ sits one halving below certainty and carries 1 bit; an event with $p = \tfrac14$ sits two halvings down and carries 2 bits; an event with $p = \tfrac18$ sits three halvings down and carries 3 bits. Each halving of the probability adds exactly one bit. Because improbable events are the surprising ones, this quantity is informally called the surprise of the event.

The logarithm is forced by an additivity requirement. Learning the outcomes of two unrelated events is the same as learning one outcome and then the other, so the information from the pair must be the sum of the information from each. Two events are independent when neither changes the odds of the other; two coin flips are the standard example. Probabilities of independent events multiply: each flip has $p = \tfrac12$, so any particular pair of flips has $p = \tfrac12 \times \tfrac12 = \tfrac14$. The first flip's report carries 1 bit and the second's carries 1 bit, so the pair's report must carry 2 bits, and it does: $-\log_2 \tfrac14 = 2$. The logarithm is precisely the function that turns multiplied probabilities into added bits: $\log(ab) = \log a + \log b$.

The same arithmetic covers events of any rarity. A 1-in-14,000,000 lottery jackpot has $p \approx 2^{-23.7}$: certainty must be halved about 24 times to reach one chance in fourteen million, so the message announcing a win carries $-\log_2(1/14{,}000{,}000) \approx 23.7$ bits. The slider below sets the probability of an event, and the readout shows the information a report of that event carries. Try the chips: each one sets the slider to the probability of a named event. The lottery chip reproduces the 23.7 bits just computed, and moving the slider toward a probability of 1 shows the information in a report falling toward zero.

2 Entropy: average information

Lesson 1 measured the information carried by a single outcome. A source of events, such as a coin or a keyboard, produces a stream of outcomes, and its entropy is the average information per outcome, weighted by how often each outcome occurs.

The sum runs over every possible outcome $x$. Each outcome's information, $-\log_2 p(x)$, is weighted by how often it occurs, $p(x)$, so $H$ is the average information per symbol, in bits. A probability-weighted average like this is called an expected value; it is the value the long-run average converges to over many draws.

A worked example makes the average concrete. A source has four symbols: A appears half the time, B a quarter of the time, C and D an eighth each. By lesson 1, these outcomes carry 1, 2, 3, and 3 bits respectively, and the entropy weights each amount by how often its outcome occurs:

A occurs often but carries only 1 bit, so it pulls the average down; D carries 3 bits but occurs an eighth of the time, so it contributes little. The average is 1.75 bits per symbol, below the 2 bits of an even four-way split, because this source has structure. Lesson 5 returns to this source and compresses it, symbol for symbol.

A coin has only two outcomes, so its whole distribution is determined by one number, $p = P(\text{heads})$, and entropy becomes a function of that number alone: $H(p) = -p \log_2 p - (1-p)\log_2(1-p)$, the binary entropy. It is the curve plotted under the widget, and it reappears at the center of lesson 6's capacity formula.

Drag the bias slider and watch the stream of flips. A fair coin is maximally unpredictable: every flip carries a full bit. A coin that lands heads 95% of the time produces a repetitive stream in which each flip carries almost no information, and the entropy falls toward zero.

3 The shape of uncertainty

A distribution is the whole table at once: every outcome a source can produce, paired with its probability. Entropy is a property of that entire shape; moving probability between outcomes moves the number. The widget below shows a distribution over 8 outcomes whose bars can be dragged into any shape.

Three shapes are worth trying deliberately. Spread probability evenly across all 8 outcomes and entropy reaches its maximum of $\log_2 8 = 3$ bits: every outcome is an equally good guess, so each draw resolves the most uncertainty a draw can resolve. Pile everything onto one bar and entropy falls to zero, because the next draw is certain and its outcome carries no information. Park half the probability on each of two bars and entropy is exactly 1 bit, however many empty outcomes sit alongside, because the source has become a fair coin.

The uniform distribution has the highest entropy because any structure, such as a bar taller than the rest, makes some outcomes more predictable than others, and entropy measures only the unpredictability that remains. The same number has a practical reading: lesson 5 shows it is the size of your data once a compressor has removed that predictability.

4 A bit is a yes/no question

Entropy has an operational meaning: it is the smallest number of yes/no questions needed, on average, to identify an unknown value. The bound is met exactly when ideal halving questions exist, as they do here, and within one question of it in general. Each well-chosen question halves the remaining possibilities, and lesson 1 showed that each halving of probability corresponds to exactly one bit.

The widget below plays this out. Think of a whole number from 1 to 64 and answer each question honestly; the page identifies your number in exactly 6 questions, because $\log_2 64 = 6$. No strategy can reliably do better, because the limit is informational: the uncertainty itself sets it.

Two refinements make the claim exact. When the count is not a power of two, the question count rounds up logarithms ↗: identifying one of 1,000 possibilities takes $\lceil \log_2 1000 \rceil = 10$ questions, because $2^9 = 512$ falls short and $2^{10} = 1024$ covers it. When outcomes are not equally likely, entropy is the average over many rounds: lesson 2's 95/5 coin has $H \approx 0.29$ bits per flip, and although no one can ask 0.29 of a question, one question can cover a whole run of flips (“were the next four all heads?”, usually answered yes), which brings the average well under one question per flip. Driving that average all the way down to $H$ is precisely the compression problem, the subject of the next lesson.

5 Entropy is the limit of compression

Shannon's source coding theorem states that a source with entropy $H$ cannot be compressed below $H$ bits per symbol on average if the compression is lossless, meaning the original is recoverable exactly, bit for bit, and that codes exist approaching this bound arbitrarily closely. Entropy is not a metaphor for information content; it is the size of the data once all redundancy, the structure and bias a code can exploit, has been removed.

The mechanism deserves a close look, because two later lessons stand on it. An ideal code assigns outcome $x$ a codeword of $-\log_2 p(x)$ bits, a length equal to the information the outcome carries. Lesson 2's four-symbol source shows how: A ($p = \tfrac12$) receives a 1-bit code, B ($\tfrac14$) a 2-bit code, and C and D ($\tfrac18$ each) 3-bit codes. Concretely, the codewords are A=0, B=10, C=110, D=111. Frequent symbols receive the short codes, rare symbols the long ones, and no codeword is a prefix of another, so the stream decodes unambiguously. The average length is $\tfrac12\!\cdot\!1 + \tfrac14\!\cdot\!2 + \tfrac18\!\cdot\!3 + \tfrac18\!\cdot\!3 = 1.75$ bits per symbol, which is lesson 2's entropy, achieved exactly. When probabilities are not powers of ½, whole-bit codewords cannot match every ideal length perfectly, which is why the theorem says approaching the bound: the best whole-bit code, Huffman's, always lands between $H$ and $H+1$ bits per symbol.

Type in the box below. The lab measures the character distribution of your text, computes its entropy, and builds a real Huffman code. Watch the table: each character's code length tracks its information content $-\log_2 p$, so frequent characters get the short codes. Compare the result against a fixed-length code that ignores the statistics entirely.

6 Noisy channels and capacity

Real channels corrupt what they carry. The simplest model is the binary symmetric channel, which flips each transmitted bit with probability $p$. Shannon's second theorem says such a channel still has a precise capacity, a maximum rate of reliable communication:

$p$ is the flip probability and $H(p)$ its binary entropy (lesson 2), the uncertainty the noise adds to each transmitted bit. One use means one bit pushed through the channel. A noiseless binary channel carries 1 bit per use; the capacity is what remains after subtracting the entropy of the noise.

A worked point makes the formula concrete. At flip probability $p = 0.11$ the noise adds $H(0.11) \approx 0.5$ bits of uncertainty to every transmitted bit, so $C \approx 0.5$: two uses of the channel deliver at most one bit that arrives reliably. The stronger half of the theorem is that this remaining rate is fully usable: at any rate below capacity, error-correcting codes can make the error probability as small as desired with no further loss of rate, and this result is what makes reliable communication over noisy links possible. Raise the flip probability below and watch the capacity fall along the curve.

7 KL divergence: the cost of a wrong model

Lesson 5 showed that an ideal code assigns outcome $x$ a codeword of $-\log_2 p(x)$ bits, with code lengths sized to the true probabilities. A code sized to the wrong probabilities does worse: when the code is built for a model $Q$ but the world actually follows $P$, each symbol is encoded in $-\log_2 q(x)$ bits while reality produces outcomes at its own rates, and the smallest possible average was $H(P)$. The average excess code length is the Kullback–Leibler divergence:

$p(x)$ is the real distribution and $q(x)$ the model's. The log ratio is the extra code length, in bits, when outcome $x$ is encoded with a code sized for $q$ instead of $p$; the sum weights those excesses by how often reality produces each outcome. Individual terms can be negative, for outcomes the model treats as more probable than they are, but the total never is.

The middle readout below shows the average code length the mismatched code actually produces, $-\sum_x p(x)\log_2 q(x)$ bits per symbol; lesson 9 gives that quantity its own name. The divergence is also direction-sensitive. If reality is lopsided, $P = (0.9,\, 0.1)$, and the model spreads its probability evenly, $Q = (0.5,\, 0.5)$, the divergence is $D(P \parallel Q) \approx 0.53$ bits. With the roles swapped, reality uniform and the model confidently lopsided, the divergence is $D(Q \parallel P) \approx 0.74$ bits. The confident error diverges more because reality does the weighting: terms where $p$ is large and $q$ is small combine a large log ratio with a large weight, and they dominate the sum.

Reality $P$ is fixed by the world; the model $Q$ is yours to shape. Drag the purple bars and watch the divergence respond. Match $Q$ to $P$ exactly and the divergence reaches zero, the only point at which it ever does.

8 Mutual information: what X says about Y

The weather and the umbrellas on the street are correlated: the state of one carries information about the other. To make this precise, each quantity is treated as a random variable, something that takes some value with some probability each time it is observed: $X$ for the sky, $Y$ for the umbrella. Each variable has an entropy of its own, written $H(X)$, the entropy of its distribution, and the pair observed together has a joint entropy $H(X,Y)$, the uncertainty of both at once. Mutual information measures how many bits the two share:

$H(X)$ and $H(Y)$ are the entropies of each variable alone; $H(X,Y)$ is the entropy of the pair. If $X$ and $Y$ were independent, the pair's entropy would be the full sum $H(X) + H(Y)$. Any shortfall means the two variables share information, and that shortfall is exactly $I(X;Y)$.

The widget below simulates a town where it rains with some probability and a citizen who matches their umbrella to the sky with some reliability. At reliability 0.5 the umbrella is a coin flip, the streams are unrelated, and $I = 0$. At reliability 1.0 the umbrella is a perfect copy of the weather and shares all of its entropy. (At reliability 0 the mutual information is just as large, because the umbrella inverts the weather deterministically, and an invertible mapping loses nothing.)

The same number has two readings. As overlap, $I$ is the shortfall between $H(X) + H(Y)$ and the joint entropy. As a question answered, $I(X;Y) = H(Y) - H(Y \mid X)$ is your uncertainty about the umbrella minus what remains of it once you have seen the sky (that remainder is called conditional entropy). The widget also restates lesson 6: an umbrella matched to the weather with reliability $r$ is exactly lesson 6's binary symmetric channel with flip probability $1 - r$, weather in, umbrella out. The identity extends to the definition of capacity: a channel's capacity is the maximum of $I(\text{input};\, \text{output})$ over all input distributions, so capacity is mutual information at its best case.

9 Cross-entropy: the loss that trains neural networks

A classifier looks at a photo and predicts a distribution $Q$ over labels. The world supplies the truth $P$. The average code length that the model's probabilities produce against that truth is the cross-entropy, and it splits into two quantities from earlier lessons:

Each outcome is encoded in $-\log_2 q(x)$ bits, a length set by the model's probabilities, but occurs at reality's rate $p(x)$. The decomposition on the right splits the total into the unavoidable part, $H(P)$, which is reality's own entropy, and the avoidable part, the KL divergence from lesson 7.

Nearly every neural network, GPT included, is trained by minimizing exactly this quantity; in machine learning it also goes by log loss, since it is the average of $-\log q$ at the true answers. Because $H(P)$ is fixed by reality, minimizing cross-entropy is the same as minimizing the KL divergence from lesson 7: training moves the model's distribution toward the truth. Drag the model's bars yourself, or press train and watch real gradient descent do it.

★ Final quiz

The quiz draws ten questions from a larger bank, and a retake draws a fresh set. Your best grade is saved with your course progress, and every answer comes with its reasoning.