Entropy and the Shortest Code

Most bounds in this subject are loose. You prove that an error is at most something, the something is enormous, and the value of the result is the shape rather than the number.

Entropy is not like that. It is the shortest that any code can be on average, and there is a code that reaches it.

The claim, on a source you can check by hand

Take four symbols with probabilities $\tfrac12$, $\tfrac14$, $\tfrac18$, $\tfrac18$. The entropy is

$$H = \sum_x p(x)\log_2\frac{1}{p(x)} = \tfrac12(1) + \tfrac14(2) + \tfrac18(3) + \tfrac18(3) = 1.75 \text{ bits}$$

Now build the best prefix code - a code where no word is the start of another, so the stream can be read without separators. Repeatedly merge the two least likely symbols and you get lengths of 1, 2, 3 and 3 bits, which is an average of

$$0.5(1) + 0.25(2) + 0.125(3) + 0.125(3) = 1.75 \text{ bits}$$

Exactly the entropy, to every decimal place. A fixed-length code would need 2 bits per symbol, so the saving is 0.25 bits, or 12.5%.

The reason the match is exact is visible in the arithmetic: each ideal length $\log_2(1/p)$ is a whole number here, because every probability is a power of two. The code can afford to give each symbol precisely the length it deserves.

What the bound actually says

$$L \ge H \quad \text{for every uniquely decodable code}$$

Two halves are worth separating. The converse says no code can do better - not a cleverer tree, not a different alphabet, not a scheme nobody has invented. The achievability says a code exists that comes within one bit, and gets arbitrarily close with the trick below.

That combination is why entropy is a modelling tool rather than a summary statistic. If some compressor beats the entropy you computed, the theorem is not in trouble: your distribution was wrong. Usually it assumed independence that is not there, and the compressor found the structure you failed to model.

Where whole bits are too lumpy

Change the source to $(0.6,\ 0.25,\ 0.1,\ 0.05)$. The entropy is 1.4905 bits, and the best prefix code averages 1.5500. A gap of 0.0595 bits per symbol has appeared.

Nothing is wrong with the code; it is provably optimal among prefix codes for that source. The problem is granularity. The ideal length for a symbol of probability 0.6 is $\log_2(1/0.6) = 0.737$ bits, and no code word is 0.737 bits long. The best you can do is 1, and you overpay by 0.263 bits every time that symbol appears.

The figure below builds the code rather than quoting it, for whatever distribution you set. Start on the dyadic source and the gap is exactly zero. Move any probability off a power of two and a gap appears at once, and the right-hand column shows why: the length each symbol deserved beside the whole number it had to be given. Then raise the block size and watch the gap close from above while the entropy per symbol does not move at all.

The trick that closes it

Stop coding one symbol at a time. Code blocks of them, and the rounding error is shared across the block:

Approaching from above, never crossing.

It is worth being precise about why this works, because the obvious explanation is wrong. The symbols here are independent, so there is no redundancy between them for a longer block to exploit, and the entropy per symbol does not change. What changes is that a block of four has 256 possible values, whose ideal lengths can be matched much more finely by whole numbers of bits. The waste is the same fraction of a bit spread over four times as many symbols.

What entropy is measuring

It is tempting to read entropy as disorder, and the reading does no harm until it does. The precise statement is the average number of yes-or-no questions you need to identify the outcome, when you are allowed to choose the questions optimally.

That framing explains the shape of the formula. A symbol of probability $p$ carries $\log_2(1/p)$ bits, so a certainty carries zero and a one-in-a-million event carries about 20 bits. Rare events are informative precisely because they were unexpected, and entropy is the average of that surprise over everything the source can do.

It also explains what entropy is not: a property of a string. A file has no entropy. A source has entropy, and your estimate of it is a statement about the model you brought.

What this sets up

Everything above assumed you know $p$. You never do. The next lesson asks what happens when you code a source with the best code for the wrong distribution, and the answer turns out to be the loss function every classifier you have trained was already minimising.