Information Theory

If we continue this line of thought, our wish list for some kind of measure of information content might be:

…​and so on, leading to Cox’s Theorem, from which we conclude:

However, information theorists take logarithms of probabilities before working with them. In his seminal paper A Mathematical Theory of Communication, Claude Shannon cites Hartley, Transmission of Information, and observes in the context of communication, logarithms better dovetailed with:

We make a couple more aesthetic choices. Firstly, the information content ought to go up when a fact is harder to guess. Thus we start with reciprocals of probabilities, or equivalently, discard the minus signs after taking logarithms of probabilities.

Secondly, as Shannon had computers in mind, he chose binary logarithms (base 2 logarithms), and called the unit of information a bit, a word coined by John Tukey.

The Shannon information content of an outcome \(x\) is:

\[ h(x) = \lg \frac{1}{P(x)} \]

where \(P(x)\) is the probability of \(x\) occurring.

One reason binary logarithms suit computers is because they can be calculated with an algorithm that suits binary arithmetic:

The first phase finds the whole number part of the logarithm, and is the same as taking the mantissa or scanning for the first 1 bit. And in the second phase, apart from one squaring operation, the multiplications and divisions are bit shifts.

However, this article avoids bit twiddling and instead uses a method based on the Taylor series expansion of \(\coth^{-1}\).

Thanks to a logarithm law, we compute the Shannon information content with:

See David Mackay, Information Theory, Inference and Learning Algorithms for more motivating examples, such as the guessing game Battleship.

Let \(X\) be a random variable and \(\mathcal{A}_X\) the set of possible values of \(X\). We call \(\mathcal{A}_X\) the alphabet of \(X\). (This term can be a tad confusing when \(\mathcal{A}_X\) is something like the set of all 5-letter words!)

We write a function that samples from a distribution given a random number in [0..1). We do the obvious, and use the cumulative sums of the probabilities. But less obvious is why we bother sorting them first; this will turn out to be useful when looking at lossy compression.

We wrap JavaScript’s Math.random() so there’s a few yaks to shave: my compiler can only talk to JavaScript via strings, so I wrote a one-off parser.

We can now flip coins and roll dice. Let the games begin!

The entropy of \(X\) is the average information content:

\[ H(X) = \sum P(x) h(x) [x \in \mathcal{A}_x] \]

Entropy can be interpreted as a measure of "uncertainty" or "ignorance": the higher it is, the more uniform the probability distribution and the harder it is to predict an outcome. For example, most of the time, we can correctly predict the result of flipping a heavily biased coin, while we must be wrong about half the time when predicting a fair coin. The latter distribution has higher entropy than the former.

Shannon proves that \(H(X)\) is the only function that satisfies the following conditions:

\[ H\left(\frac{1}{2}, \frac{1}{3}, \frac{1}{6}\right) = H\left(\frac{1}{2}, \frac{1}{2}\right) + \frac{1}{2} H\left(\frac{2}{3}, \frac{1}{3}\right) \]

See also Chapter 11 of Jaynes, and John Carlos Baez, What is Entropy?

The principle of maximum entropy guides us when groping blindly in the dark. If there are \(n\) possible outcomes and we are completely ignorant, then we have no reason to prefer any outcome over any other. Accordingly, we assign each outcome the same probability \(1/n\), corresponding to maximum entropy. If, after some exploration, we become less ignorant and are aware of constraints on the probability distribution, then we should assign probabilities that simultaneously satisfy the constraints and maximize the entropy.

For example, suppose we have a normal-looking die with faces labeled 1 to 6. Initially we maximize entropy by guessing each face shows up with probability 1/6. Suppose we somehow learn the mean value of rolling our die is 4.5. This is greater than 3.5, the mean value of rolling a fair die, thus our die is unfair. Then how should we revise the probabilities?

We could, say, assign 0.7 probability to 6 and 0.3 to 1, and claim no other face ever shows up, but is this sensible? While an expected value of 4.5 implies higher numbers are more likely than lower numbers, it’s strange to rule out the faces from 2 to 5. Intuitively, we ought to instead modify the uniform distribution as gently as possible, nudging up the probabilities of larger faces showing and nudging down the smaller ones. Zealously zeroing some probabilities is too extreme.

It turns out we maximize entropy with a Boltzmann distribution:

If our code is right, then the sum of 100 rolls should usually be close to 450, instead of 350, which would result from a fair die:

We compute the entropies of:

Information theory is crucial for understanding data compression: lossy compression; symbol codes; stream codes. The entropy of a distribution pops up again and again in theoretical limits. But for now, we just say a few words about uncompressed data to establish a baseline.

The raw bit content of \(X\) is:

\[ H_0(X) = \lg |\mathcal{A}_X| \]

This measures the space needed to record one symbol of \(X\).

Exercise: Show \( 0 \le H(X) \le H_0(X) \). When do we have equality on either side?

The answers follow directly from the mathematics, but we can interpret them qualitatively. Consider a lopsided distribution where one symbol almost always appears while the others are rare. Then the average symbol will be the common one, which gives us almost no information. In the extreme case, the other symbols are impossible so we learn nothing from the only symbol that exists. In contrast, if the distribution is uniform, we have no idea what symbol to expect next (assuming at least two symbols).

Let’s explore these ideas with the relative letter frequencies in English:

We turn this into a probability distribution with a primitive parser:

Without spaces, English text takes about 4.7 bits per character, though its information content is less than 4.18 bits per character.

We emphasize that these numbers are derived solely from single-letter frequencies. In reality, English text has far less information content, as many dependencies exist between the constituent letters.

This is clear if we generate some 5-letter "words":

Even though the frequencies of individual letters are about right, these words almost certainly never occur in English; the probability of sampling such words should really be zero.

Evidence suggests humans send information at 39 bits per second when speaking. If we assume humans read English at 238 words per minute and the average English word length is 4.8 letters, then we roughly read 20 letters per second:

If the rate we read information is about the same as we speak it, then English transmits about 2 bits of information per character:

When Shannon studied the entropy of English, he arrived at 2.62 bits per character.