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.
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.
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.
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.
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.
| chance | surprise, bits | chance × surprise |
|---|
Uncertainty is greatest, at 1 bit, when the two outcomes are equally likely, and falls to zero as either becomes certain.
Shannon's uniqueness theorem in four steps
Let be the uncertainty of a choice among outcomes with probabilities .
What is assumed
- Continuity. is continuous in the .
- Monotonicity. increases with .
- Grouping. If a choice is made in two stages, is the uncertainty of the first stage plus the uncertainties of the second-stage choices, each weighted by the probability that it arises.
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.
What the theorem does and does not say
- It measures uncertainty, and nothing else. The number depends only on the probabilities. It says nothing about what the outcomes mean or how the probabilities were arrived at.
- Shannon himself did not emphasize it. He remarked that the theorem was not needed for the rest of his theory. For him the measure earned its place through what it predicts about coding and communication.
- The grouping requirement does the work. Faddeev showed in 1956 that continuity and grouping are enough on their own. Weaken the grouping requirement and other measures become possible, such as the Rényi entropies.
- It does not say which probabilities to use. A separate set of consistency requirements, due to Shore and Johnson, addresses when choosing probabilities by maximizing entropy is the right way to infer them.
Sources:
- C. E. Shannon, "A mathematical theory of communication," Bell System Technical Journal 27 (1948), pp. 379–423 and 623–656. The three requirements are in section 6 and the proof in Appendix 2, which this page follows.
- A. I. Khinchin, Mathematical Foundations of Information Theory (1957).
- A. Rényi, "On measures of entropy and information," Proceedings of the Fourth Berkeley Symposium on Mathematical Statistics and Probability, vol. 1 (1961), pp. 547–562.
- J. E. Shore and R. W. Johnson, "Axiomatic derivation of the principle of maximum entropy and the principle of minimum cross-entropy," IEEE Transactions on Information Theory 26 (1980), pp. 26–37.
- T. Leinster, Entropy and Diversity: The Axiomatic Approach (2021), for Faddeev's theorem.