Why Does the Entropy Formula Have a Logarithm?

Foundations of Information Theory · Part 2

An intuitive derivation of the entropy formula: why uncertainty must be measured with a logarithm, and why entropy is the average surprise of a source.

Most of us meet entropy as a formula to be memorised:

H(X) = \sum_i p_i \log_2 \frac{1}{p_i}

But why a logarithm? Why not something simpler? On this page we build the formula step by step, so that by the end it feels less like a definition and more like the only sensible answer.

Rare events carry more doubt

Think about a single event. If its probability is close to one, we expected it, and when it happens we are hardly surprised. If its probability is close to zero, its occurrence is very surprising.

So whatever we use to measure our doubt about an event, it should become smaller as the probability becomes larger. The most natural first guess is the reciprocal of the probability, 1/p. If p = 0.01, this gives 100; if p = 0.99, it gives only 1.01. So far, so good.

The first guess fails

Now suppose a transmitter sends two independent bits. The probability of a particular pair is the product of the individual probabilities,

p_{\text{joint}} = p_1 \times p_2,

so our first guess also becomes a product:

\frac{1}{p_{\text{joint}}} = \frac{1}{p_1} \times \frac{1}{p_2}.

But if one bit, decoded perfectly, gives the receiver one bit of information, then two bits should give it two: one plus one. Information should add, while probabilities multiply.

We need a function that turns products into sums. The only well-behaved function that does this is the logarithm.

Surprise

We therefore define the surprise of an outcome with probability p as

S(p) = \log_2 \frac{1}{p},

measured in bits. An outcome with probability \tfrac12 has a surprise of 1 bit, \tfrac14 gives 2 bits, and \tfrac18 gives 3 bits: each time the probability halves, the surprise grows by exactly one bit. For two independent events, the surprises now add, S(p_1 p_2) = S(p_1) + S(p_2), exactly as information should. This line of reasoning goes back to Claude Shannon’s 1948 paper, which founded information theory.

From one outcome to the whole source

Surprise belongs to a single outcome. To describe a whole source, we take the average surprise, weighting each outcome by how often it occurs. This average is the entropy:

H(X) = \sum_i p_i \log_2 \frac{1}{p_i}

For a binary source that sends a 1 with probability q, the entropy is largest, exactly 1 bit, when q = \tfrac12. If the source sends a 1 ninety percent of the time, its entropy drops to about 0.469 bits: it is more predictable, so there is less uncertainty to remove.

Binary entropy curve rising from zero at q = 0 to one bit at q = 0.5 and back to zero at q = 1. — Figure 1: The entropy of a binary source. It is zero when the output is certain, and largest when both values are equally likely.

This shows something easy to miss: a binary digit carries at most one bit of information, and exactly one bit only when 0 and 1 are equally likely.

Why not just average 1/p?

A natural question is why we could not keep the first guess and simply average it. Each term would be p_i \cdot \frac{1}{p_i} = 1, so the average of 1/p just counts the outcomes. A fair three-sided source and one that almost always produces the same symbol would both score 3, even though the second is nearly predictable. Their entropies are very different: about 1.585 bits and 0.161 bits. The logarithm is needed for both reasons.

Previous: What is information? A noisy channel and a puzzle

Next: What is conditional entropy? Solving the noisy-channel puzzle

Back to the series: Foundations of Information Theory

Read the full chapter, with worked problems: Chapter 1 (PDF)