Information Theory

Claude Shannon had already shown, in his master's thesis of 1937, that Boole's logic could design switching circuits. In 1948, at Bell Labs, he published "A Mathematical Theory of Communication". It brought probability into Hartley's measure. The information in a source is its entropy, $H = -\sum p_i \log_2 p_i$, in bits, a name Shannon credited to his colleague John Tukey. He proved that a source can be compressed to $H$ bits per symbol and no further. Then came the surprise. Every noisy channel has a capacity, and below it information can be sent with as few errors as desired, not by slowing down but by coding long blocks cleverly. His proof picked a code at random and showed it works on average. It proved that good codes exist without exhibiting one.

Others took up the search. In 1950 Richard Hamming, tired of Bell Labs computers giving up on weekend jobs at the first error, published codes that correct errors themselves. In 1952 David Huffman, a student who chose a term paper over an exam, found the optimal way to compress a source with known probabilities. The gap to capacity stayed wide for decades.

A fair coin needs one bit per toss: nothing can be saved. Now take a coin that lands heads with probability 0.9. Its entropy is

$$H = -0.9 \log_2 0.9 - 0.1 \log_2 0.1 \approx 0.469 \text{ bits per toss},$$

so Shannon's theorem says a long record of tosses can be stored in less than half the space. How do we get there? One symbol at a time we cannot: any code must use at least one bit per toss. The trick is to code blocks. Take pairs of tosses:

Pair	Probability	Huffman codeword	Length
HH	0.81	0	1
HT	0.09	10	2
TH	0.09	110	3
TT	0.01	111	3

Huffman's rule builds this table by repeatedly merging the two least likely entries: TT with TH, then that pair with HT, then everything with HH. The average length is $0.81 \times 1 + 0.09 \times 2 + 0.09 \times 3 + 0.01 \times 3 = 1.29$ bits per pair, or 0.645 bits per toss, already a saving of about a third. With blocks of three tosses the Huffman code needs 0.533 bits per toss, and longer blocks approach 0.469 as closely as desired, but never beat it. That limit is the entropy.

The same measure applies to language. Twenty-six letters and a space would need $\log_2 27 \approx 4.75$ bits each if all were equally likely. But English is predictable: after "q" comes "u". In 1951 Shannon asked people to guess the next letter of a text and estimated that English carries only about one bit per letter, so most of its letters could, in principle, be predicted from what came before. That redundancy is why a text with some letters missing can still be read, and why it compresses so well.

In 1965 Andrey Kolmogorov, independently of Ray Solomonoff and Gregory Chaitin, defined the information in a single string as the length of the shortest program that prints it. The idea tied information to computability theory: the complexity of a string is itself uncomputable. Kolmogorov also carried Shannon's entropy into ergodic theory as a measure of chaos.

Shannon's limit was finally approached in practice in 1993, when Claude Berrou and his colleagues announced turbo codes. David MacKay and Radford Neal then showed that Robert Gallager's low-density parity-check codes of 1962, built from the sparse random graphs of probabilistic combinatorics, were just as good. Entropy has also returned to physics, where erasing a bit is known to cost energy, as non-equilibrium physics describes. And the question of how much information a finite sample carries about a whole distribution lies at the root of statistical learning theory.