Shannon's entropy

How to quantify
uncertainty

How uncertain are you about what will happen next? Claude Shannon wanted a number for that, depending only on the probabilities of the possible outcomes. In 1948 he wrote down three things such a number ought to do. It should change smoothly as the probabilities change. With equally likely outcomes, more of them should mean more uncertainty. And if you make a choice in stages, the uncertainty should come to the same total as making it all at once.

Those three requirements leave exactly one formula, , up to the choice of unit. Four figures come first, to build intuition. The proof follows.

Figure 1 · Two routes must agree

A choice made in stages has to carry the same uncertainty as the choice made at once

Pick one of three outcomes. You can do it in a single three-way choice. Or you can first decide between the first outcome and "one of the other two," and then, only if needed, decide between those two. Both describe the same situation, so a sensible measure H must give both the same uncertainty. For the staged route, the second choice counts only for the fraction of the time it actually happens.

The starting values are Shannon's own example: probabilities 1/2, 1/3 and 1/6, or a fair coin followed half the time by a 2/3 against 1/3 choice.

The other three candidates are all reasonable-sounding measures of spread, but each gives two different answers for the same situation, at least for some settings of the sliders. Only the first survives, for every setting of the sliders.

Figure 2 · Equally likely outcomes

When the options multiply, the uncertainty has to add

Start with the simplest case, where every outcome is equally likely. Write A(n) for the uncertainty of a choice among n equally likely options. Picking one cell from a grid with m rows and n columns is a choice among m × n options. It is also a choice of row followed by a choice of column. By Figure 1 the two must agree, so A(m × n) = A(m) + A(n).

candidate A(n)A(m)A(n)A(m) + A(n)A(m × n)

The line at the bottom marks m, n and m × n on a scale where each doubling of the options is one equal step. On that scale the two lengths laid end to end reach the product.

Only a logarithm turns multiplying into adding. Every doubling of the options adds the same fixed amount of uncertainty, and that amount is the unit. Taking it to be 1 gives the bit: two equally likely options are 1 bit, four are 2 bits, eight are 3.

Figure 3 · From equal chances to unequal ones

An unequal choice is an equal choice with the cells grouped

Now for outcomes that are not equally likely. Take a row of equally likely cells and paint them in groups. Picking a cell at random lands in a group with probability proportional to its size, so the groups are outcomes with unequal chances. Picking a cell is a two-stage choice: first which group, then which cell inside it. By Figure 1 the uncertainties add, and by Figure 2 we know both the total and the second stage. What is left over is the uncertainty of the unequal choice.

Top: the cells, colored by group. Bottom: the uncertainty of picking a cell, split into "which group" and "which cell inside the group." The second part is an average, with each group counted by how often it comes up.

Read off the left-hand piece: H = log N − Σ p log(cells in the group). Since each group's probability is its cells divided by N, this is the same as H = −Σ p log p.

Figure 4 · The result

Entropy is the average surprise

The formula has a direct reading. An outcome with probability p carries a surprise of log₂(1/p) bits: none if it was certain, 1 bit if it was a coin flip, more as it gets rarer. Entropy is the surprise you should expect, each outcome's surprise weighted by its chance. For a choice between two outcomes it looks like this.

chancesurprise, bitschance × surprise

Uncertainty is greatest, at 1 bit, when the two outcomes are equally likely, and falls to zero as either becomes certain.

The proof

Shannon's uniqueness theorem in four steps

Let be the uncertainty of a choice among outcomes with probabilities .

What is assumed

1. Equally likely outcomes: products become sums

A choice among equally likely outcomes can be staged as a choice among equally likely groups followed by a choice among the equally likely members of the chosen group. Each group arises with probability , so grouping gives

Taking shows , and repeating the step gives .

2. So A is a logarithm

Fix integers . For any choose with . Since increases from , . Monotonicity and step 1 give . Taking logarithms of the same inequalities gives . Dividing through,

Two numbers in the same interval of width differ by less than , and is arbitrary. So , which means

for a constant . Monotonicity makes .

3. Rational probabilities

Let with whole numbers adding up to . Split equally likely outcomes into groups of sizes . Choosing an outcome is choosing a group, which has uncertainty , and then choosing among the equally likely members of that group. Grouping gives

Solve for and use step 2:

4. All probabilities

Every set of probabilities can be approached by rational ones, and both sides of the last equation are continuous. So it holds in general:

Conversely this formula is continuous, gives , which increases, and satisfies grouping, as a direct calculation shows. The constant only sets the unit. With and logarithms to base 2, the unit is the bit.

Fine print

What the theorem does and does not say

Sources: