Entropy

The average information content of an ensemble, and the quantity both coding theorems are stated in. H(X) = Σᵢ pᵢ log₂(1/pᵢ), in bits, where the ensemble X is a set of outcomes {a₁ … a_I} with probabilities {p₁ … p_I}.

Sourced from information-theory-inference-learning-algorithms, held in ../machine-learning-wiki (see the provenance note on information-theory).

Why the logarithm

Not a convention. The Shannon information content of a single outcome is h(x) = log₂(1/p(x)), and the logarithm is forced by wanting information to add. For independent x and y, P(x,y) = P(x)P(y), so

h(x,y) = log 1/P(x)P(y) = log 1/P(x) + log 1/P(y) = h(x) + h(y)

and entropy inherits the property: H(X,Y) = H(X) + H(Y) for independent variables. Any other function of p breaks additivity, which is the property that lets you count bits.

The binary entropy function H₂(p) = p log₂(1/p) + (1−p) log₂(1/(1−p)) is the entropy of a single biased bit and shows up in nearly every result: it is the capacity loss of a noisy binary channel, the exponent of the typical set, and the rate a bounded-distance decoder gives away.

The quantities built on it

• Joint entropy H(X,Y) — the uncertainty in the pair.
• Conditional entropy H(X|Y) — the uncertainty left in X after seeing Y, averaged over Y.
• Mutual information I(X;Y) = H(X) − H(X|Y) = H(Y) − H(Y|X) — how much observing Y reduces uncertainty about X. Symmetric, non-negative, and the quantity maximised to define channel capacity in noisy-channel-coding-theorem.

MacKay's practical note: think of I(X;Y) as H(X) − H(X|Y) for intuition and compute it as H(Y) − H(Y|X), because the second form is usually the easy one. Worked on a binary symmetric channel with flip probability f = 0.15 and input {0.9, 0.1}, I(X;Y) = H₂(0.22) − H₂(0.15) = 0.76 − 0.61 = 0.15 bits, against a source entropy of H₂(0.1) = 0.47 bits — most of what the source carried does not get through.

Typicality: why entropy is the right average

Entropy would be an arbitrary summary statistic if not for what happens to long sequences. Draw N outcomes independently. As N grows, the sequences you actually see concentrate in a typical set of about 2^{NH} members, each of probability about 2^{−NH} — while the individually most probable sequence usually sits outside it. For 100 draws from a source with p₁ = 0.1, the all-zeros string is the single most likely outcome and is nothing like what you get; the entropy is 46.9 bits and the samples cluster there.

This is the asymptotic equipartition principle, and it is the law of large numbers applied to log 1/P(x). Both coding theorems are proved by counting members of a typical set: the source theorem needs NH bits to name one, and the channel theorem asks whether a received sequence is jointly typical with exactly one codeword.

What it does not measure

Entropy is a property of the ensemble, not of the object. It needs a probability distribution before it says anything, so "the entropy of this file" is shorthand for "the entropy of the source model I am assuming for this file" — which is exactly why compression and modelling are the same activity in source-coding-theorem. A different model of the same data gives a different number and a different compressed length.

Related

information-theory · source-coding-theorem · noisy-channel-coding-theorem · probability-theory · claude-shannon · information-theory-inference-learning-algorithms · mathematics · synthesis