A Mathematical Theory of Communication (Part 1)

Two random strings, both produced by chance operations:

XFOML RXKHRJFFJUJ ZLPWCFWKCYJ
THE HEAD AND IN FRONTAL ATTACK ON AN ENGLISH WRITER

The first picks each character uniformly from Shannon's twenty-seven-symbol alphabet, the twenty-six letters and a space. The second picks words, weighted by English word frequencies and word-to-word transitions. Still random, but in the second string English has already done some of the selecting; the source has fewer live choices at each step. How many fewer? How much choice is left?

That is the number Claude Shannon, a thirty-two-year-old Bell Labs mathematician, made public in 1948 with A Mathematical Theory of Communication, published in two parts in the Bell System Technical Journal. It turned "information" from a loose engineering word into a number with a unit.

The move he learned at twenty-one#

To see what kind of thinker Shannon was, jump back to 1937, when his MIT master's thesis observed that Boole's algebra of and, or, and not matches the behavior of electrical relay networks, and circuit design went from a craft of trial and error to algebra. The move: take an engineering practice, find the math underneath, and let the math reorganize the practice. In 1948 he plays the same move at a much bigger scale.

The argument before Shannon#

The question had been sitting around Bell Labs for two decades. In 1924, Harry Nyquist asked what limits telegraph speed and wrote down the first logarithmic law in this story: with $m$ distinct signal levels at a fixed signaling rate, the transmittable "intelligence" (his word) is proportional to $\log m$.

Four years later Ralph Hartley, in Transmission of Information, insisted information should be a physical quantity, not a psychological one: what a message means is the receiver's problem. For $n$ equally likely messages, one selection carries $H=\log n$.

Why log? Two independent choices of size $n$ have $n^2$ joint outcomes and should carry twice the information of one, and log turns multiplication into addition: $\log n^2=2\log n$. Add continuity and log is the only function that works, up to the base, which picks the unit: base two gives bits, a name Shannon credited to John Tukey.

So by 1928 the uniform case is forced. But real sources are not uniform, and Hartley handled unequal probabilities only indirectly. For twenty years the general answer sits open.

The cryptography years#

Shannon joined Bell Labs full time in 1941, with the war on. The war work that matters here is cryptography: cryptanalysis is partly guessing plaintext from the statistics of ciphertext, which forces you out of the uniform case into distributions with structure.

In early 1943, Alan Turing spent two months at Bell Labs on classified business, meeting Shannon for tea daily. Forbidden from discussing active cryptanalysis, they talked about everything else: Turing's 1936 paper on computable numbers, Shannon's measure of information.

By autumn 1945, Shannon had written a classified memo, A Mathematical Theory of Cryptography, with the formula $H=-\sum p\log p$ already inside, three years early. He had realized two questions were one: how much information about the plaintext leaks through a ciphertext, and how much goes through a noisy channel. Both want a number. The 1948 paper is the declassified, generalized version.

Modeling a real source#

Shannon models a discrete source as a Markov process: states, a distribution over the next symbol from each state, a rule that emits and updates. Section three makes this concrete with a sequence of approximations to English. Zeroth order, uniform letters: the first string above. First order, true letter frequencies. Second order, digrams, and the output starts to look pronounceable. Third order, trigrams:

IN NO IST LAT WHEY CRATICT FROURE BIRS GROCID PONDENOME

Then a jump to whole words with word transitions, and out comes the second string above. Read with modern eyes, this is an n-gram language model, in print in 1948. Missing: a number for how much uncertainty remains at each step.

Three things he wants from the answer#

Call the number $H$, a function of the distribution $p_1,\cdots ,p_n$. On uniform distributions it should reduce to Hartley's $\log n$; on a deterministic one it should be zero. The move: write down what $H$ should do, and see what is left. Section six asks three things. One, continuity: tiny changes in the probabilities produce tiny changes in $H$. Two, monotonicity on uniform distributions: six equally likely outcomes are more uncertain than five.

Three, grouping, the one that does the work: the order in which you stage a choice cannot change the total information. Shannon's figure six: a single choice among probabilities one half, one third, one sixth equals a fair coin flip followed, half the time, by a two-thirds versus one-third choice. Same final probabilities, same uncertainty:

$$H(\frac{1}{2},\frac{1}{3},\frac{1}{6})=H(\frac{1}{2},\frac{1}{2})+\frac{1}{2}H(\frac{2}{3},\frac{1}{3})$$

The coefficient one half is there because the second choice only happens half the time.

Pause and try: use the grouping axiom to compute H(1/2, 1/4, 1/4).

Stage the choice as a fair coin flip, then on the second branch another fair flip. Grouping gives $H(\frac{1}{2},\frac{1}{4},\frac{1}{4})=H(\frac{1}{2},\frac{1}{2})+\frac{1}{2}H(\frac{1}{2},\frac{1}{2})$. Each fair flip is one bit, so the answer is $\frac{3}{2}$ bits. Check against the formula: $\frac{1}{2}·1+\frac{1}{4}·2+\frac{1}{4}·2=\frac{3}{2}$.

The forcing argument#

Three innocuous rules. Shannon's Theorem 2, proved in appendix two: the only $H$ satisfying them has the form

$$H=-K\sum _i{p}_i\log p_i$$

with $K>0$. Shannon did not define the formula; he listed what a measure of uncertainty should do, and this is what survived. He names the quantity entropy.

The proof has three phases. Phase one, equiprobable: let $A\left(n\right)$ be $H$ on the uniform distribution over $n$ outcomes. Grouping applied to a tree of $s^m$ equiprobable leaves gives $A\left(s^m\right)=mA\left(s\right)$; with monotonicity, the only solution is $A\left(n\right)=K\log n$, Hartley's measure again. Phase two: write each rational $p_i=n_i/N$ over a common denominator, group a uniform distribution over $N$ outcomes into bins of sizes $n_i$; $A\left(N\right)$ decomposes into $H\left(p\right)$ plus weighted within-bin uncertainties $K\log n_i$, and rearranging gives the formula for rational $p$. Phase three: approximate any real distribution by rationals; continuity does the rest.

Shannon is careful here. Just after Theorem 2: "This theorem, and the assumptions required for its proof, are in no way necessary for the present theory... The real justification of these definitions, however, will reside in their implications." The axioms make the form plausible. The properties justify it.

What the number does#

Section six lists six properties; three carry the meaning. $H=0$ exactly when the distribution is deterministic: nothing to be uncertain about. $H\le \log n$, with equality exactly at uniform: Hartley's measure survives as the maximum. And conditioning reduces entropy: $H\left(Y\right)\ge H(Y\mid X)$, with equality when $X$ and $Y$ are independent; the statement is about the average, since one particular value of $X$ can raise it.

Plot the binary case and you get figure seven of the paper: zero at the endpoints, maximum at one half. The rest (subadditivity, the chain rule, Schur-concavity) are working tools for later in the paper.

The cousin from physics#

A footnote at the same spot notes that $-\sum p\log p$ is also the $H$ of Boltzmann's H-theorem; Shannon cites Tolman, 1938. Same form, different physics: there the $p_i$ range over cells of phase space, here over messages.

Shannon liked to tell the naming story: he asked von Neumann what to call the quantity, and von Neumann said to call it entropy, first because the formula already has that name in physics, and second because nobody really knows what entropy is, so in any debate you will have the upper hand. Hard to verify decades later, but the joke carries a real point: the math under both is the same, count the equally likely possibilities and take a log. What differs is what counts as a possibility.

The idea outgrew the paper#

After section six, the paper proves the entropy rate is the limit of lossless compression and that even noisy channels have a capacity: the next parts of this series.

The bigger story is what the number seeded. Once you can score how uncertain one distribution is, you can score the gap between two: replace $\log p$ in the formula with $\log q$, where $q$ is a model of the truth, and you get the cross-entropy of $p$ under $q$, equal to the entropy when $q=p$ and larger when $q$ is wrong. The excess is the Kullback-Leibler divergence, introduced in 1951, now at the center of modern statistics and machine learning.

The formula spread fast: genetics, psychology, linguistics within a decade. Shannon was wary; his 1956 editorial The Bandwagon warned against loose application. He wanted a measure, and that is what he got: choice has a number, and the number is forced.

If you remember three things#

1. Hartley forced $\log n$ for equally likely messages in 1928; the non-uniform case waited twenty years.
2. Continuity, monotonicity on uniform distributions, and grouping leave only $H=-K\sum p_i\log p_i$ standing: that is Theorem 2. The formula was not chosen. It was forced.
3. Entropy was a wartime tool before it was a public theory: the formula appears in Shannon's classified 1945 cryptography memo, three years early.