Entropy: Measuring Information in Bits

The everyday word information is about meaning. Shannon's is not. In information theory, the information carried by an event is how surprised you should be to see it.

David MacKay, in Information Theory, Inference, and Learning Algorithms (Cambridge University Press, 2003), defines the Shannon information content of an outcome $x$ as $h(x) = \log_2 (1/P(x))$, measured in bits.

A certain event tells you nothing. A one-in-a-thousand event carries about 10 bits. The logarithm is the right shape for exactly one reason: independent events multiply their probabilities, and we want their surprises to add. Each halving of the probability costs precisely one more bit.

Entropy is what you get when you average that surprise over every outcome the source can produce:

$H(X) = -\sum_i p_i \log_2 p_i$

Claude Shannon introduced it in A Mathematical Theory of Communication, published in two parts in the Bell System Technical Journal, vol. 27, pp. 379-423 (July 1948) and pp. 623-656 (October 1948). He did not simply assert the formula. In Theorem 2 he shows it is the only function satisfying three requirements: continuity in the probabilities, monotonic growth in the number of equally likely choices, and consistency when a choice is split into two successive choices.

The unit comes from the same paper. Shannon writes that base 2 gives units that "may be called binary digits, or more briefly bits, a word suggested by J. W. Tukey." Bits are not an implementation detail here. They are the natural currency of binary questions.

Take a source emitting four symbols with probabilities $1/2, 1/4, 1/8, 1/8$. Term by term:

(1/2) x log2(2) = 0.5 x 1 = 0.500
(1/4) x log2(4) = 0.25 x 2 = 0.500
(1/8) x log2(8) = 0.125 x 3 = 0.375
(1/8) x log2(8) = 0.125 x 3 = 0.375
                        H = 1.750 bits

Exactly 7/4 bits. This is Example 2.1.2 in Cover and Thomas, Elements of Information Theory (Wiley), and the number is not abstract. Assign the codewords 0, 10, 110, 111 and the average length is $0.5(1) + 0.25(2) + 0.125(3) + 0.125(3) = 1.75$ bits per symbol. Entropy predicted the best possible code, and the code hit it exactly.

A fixed 2-bit-per-symbol encoding would spend 2.0 bits. The 0.25-bit gap is real, recoverable compression.

For an alphabet of $n$ symbols, entropy is maximised when all symbols are equally likely, giving $\log_2 n$ bits. Any skew in the distribution pushes entropy down, and that shortfall is exactly the redundancy a compressor can exploit.

A fair coin: $H = 1$ bit. A coin biased to 0.9 heads:

-0.9 x log2(0.9) = 0.9 x 0.15200 = 0.13680
-0.1 x log2(0.1) = 0.1 x 3.32193 = 0.33219
                             H = 0.4690 bits

Storing each flip in one literal bit wastes over half a bit per flip.

Shannon measured this for English in Prediction and Entropy of Printed English (Bell System Technical Journal, vol. 30, no. 1, January 1951, pp. 50-64). A 26-letter alphabet chosen uniformly would give 4.70 bits per letter; using real letter frequencies drops it to 4.14; and with 100 letters of preceding context his experiments bracket English between 0.6 and 1.3 bits per letter.

Two random variables give three quantities worth naming:

• Joint entropy $H(X,Y)$: total uncertainty in the pair.
• Conditional entropy $H(Y \mid X)$: uncertainty left in $Y$ once you already know $X$.
• The chain rule tying them together: $H(X,Y) = H(X) + H(Y \mid X)$.

Cover and Thomas state this as Theorem 2.2.1 in Elements of Information Theory. Shannon derived the same relation in section 6 of his 1948 paper and glossed it plainly: the uncertainty of the joint event is the uncertainty of $X$ plus the uncertainty of $Y$ when $X$ is known. He called $H(X \mid Y)$ the equivocation, which is still the term used for what a noisy channel destroys.

Conditioning never hurts: $H(Y \mid X) \le H(Y)$. Knowing something about $X$ can only leave you less uncertain about $Y$, or equally uncertain if the two are independent.

Mutual information is the drop in uncertainty about $X$ that you get from observing $Y$:

$I(X;Y) = H(X) - H(X \mid Y) = H(Y) - H(Y \mid X) = H(X) + H(Y) - H(X,Y)$

Shannon wrote all three forms in section 12 of the 1948 paper, calling the quantity the rate of transmission. It is symmetric, always non-negative, and zero exactly when $X$ and $Y$ are independent.

Worked example. Send a uniform random bit through a binary symmetric channel that flips it with probability 0.1. The receiver's leftover uncertainty is $H(0.1) = 0.4690$ bits, computed exactly as the biased coin was. So

I(X;Y) = 1 - 0.4690 = 0.5310 bits per channel use

You pushed one bit in and roughly half a bit of it survived. That number is not a metaphor; it is the channel's capacity.

Joint entropy splits into three non-overlapping pieces, and the entropies of each variable are built from them:

Kullback-Leibler divergence measures how far a model $q$ is from the truth $p$:

$D(p \parallel q) = \sum_i p_i \log_2 (p_i / q_i)$

It comes from Solomon Kullback and Richard Leibler, On Information and Sufficiency, Annals of Mathematical Statistics, vol. 22, no. 1 (March 1951), pp. 79-86.

Worked example. Truth $p = (0.5, 0.5)$, model $q = (0.8, 0.2)$:

D(p||q) = 0.5 log2(0.5/0.8) + 0.5 log2(0.5/0.2)
        = 0.5(-0.6781) + 0.5(1.3219) = 0.3219 bits

D(q||p) = 0.8 log2(0.8/0.5) + 0.2 log2(0.2/0.5)
        = 0.8(0.6781) + 0.2(-1.3219) = 0.2781 bits

The two disagree. KL divergence is not symmetric and does not obey the triangle inequality, so it is not a distance despite constantly being described as one. Cover and Thomas prove it is always non-negative and zero only when $p = q$, calling that the information inequality.

Cross-entropy is the bill for coding data drawn from $p$ using a code built for $q$:

$H(p,q) = -\sum_i p_i \log_2 q_i = H(p) + D(p \parallel q)$

Goodfellow, Bengio and Courville state this identity in Deep Learning (MIT Press, 2016, section 3.13). Continuing the example above:

H(p,q) = -0.5 log2(0.8) - 0.5 log2(0.2)
       = 0.1610 + 1.1610 = 1.3219 bits
check:   H(p) + D(p||q) = 1.0 + 0.3219 = 1.3219  OK

You pay 1.3219 bits where 1.0 would do. The excess is the KL divergence.

Because $H(p)$ does not depend on $q$, minimising cross-entropy over models is identical to minimising KL divergence, which is why cross-entropy over next-token prediction is literally the training loss for language models (Kaplan et al., Scaling Laws for Neural Language Models, 2020, describe optimising "the autoregressive log-likelihood, i.e. cross-entropy loss"). Perplexity is just that loss exponentiated: $2^{1.3219} = 2.5$.

Three traps worth avoiding:

• Entropy is a property of the distribution, not of a string. "The entropy of this file" is shorthand for the entropy of a model you fitted to it. Change the model and the number changes.
• KL divergence is not a distance. The worked example gave 0.3219 one way and 0.2781 the other. Which argument goes first matters, and the two directions penalise different failures.
• Bits versus nats. Base 2 gives bits, natural log gives nats, and $1$ nat is about $1.4427$ bits. Machine learning code defaults to nats; compression literature defaults to bits.