Shannon Entropy: The Hard Limit on How Much You Can Compress

The question entropy answers

Claude Shannon's 1948 paper “A Mathematical Theory of Communication” opens with a deceptively narrow question: if a source emits symbols drawn from some known set of probabilities, what is the smallest average number of bits per symbol any encoding scheme could possibly achieve, no matter how clever? The answer is a single formula, and it turned out to be the founding equation of an entire field.

H(X)  =  - sum over all symbols x of  p(x) * log2( p(x) )

// measured in bits per symbol
// by convention, p(x) * log2(p(x)) is taken to be 0 when p(x) = 0

Why the logarithm, and why base 2

Shannon wanted a quantity with three specific properties: it should be continuous in the probabilities, it should be maximal when all outcomes are equally likely (maximum uncertainty), and — critically — it should be additive for independent events, meaning the information content of two independent symbols together equals the sum of their individual information contents. Only a logarithm satisfies additivity for independent probabilities (because log(p*q) = log(p) + log(q)), which pins down the functional form almost uniquely; the base of the logarithm then just fixes the unit — base 2 gives bits, base e gives nats, base 10 gives hartleys. Bits is the natural choice because it directly answers “how many yes/no questions, on average, does it take to identify the outcome?”

A single fair coin flip, worked out by hand

A fair coin has p(heads) = p(tails) = 0.5, so:

H = -(0.5 * log2(0.5) + 0.5 * log2(0.5))
  = -(0.5 * (-1) + 0.5 * (-1))
  = -(-0.5 - 0.5)
  = 1 bit

A biased coin, p(heads) = 0.9, p(tails) = 0.1:
H = -(0.9 * log2(0.9) + 0.1 * log2(0.1))
  = -(0.9 * (-0.152) + 0.1 * (-3.322))
  = -(-0.137 - 0.332)
  ≈ 0.469 bits

This is the core intuition entropy captures: a fair coin genuinely costs you one full bit to communicate, because you truly cannot predict it. A biased coin that comes up heads 90% of the time is nearly predictable, so on average it costs less than half a bit — most of the time you already know it will be heads and the message barely tells you anything new. Entropy is maximised when the distribution is uniform (every outcome equally surprising) and falls toward zero as one outcome becomes near-certain (nothing left to learn).

Twenty questions, and why entropy is a hard floor, not a suggestion

The classic 20-questions game — asking only yes/no questions to identify an unknown item from a known set — is literally binary search under uncertainty, and it makes entropy concrete: the optimal strategy, at every step, splits the remaining probability mass as close to 50/50 as possible, because a question that isolates a near-certain outcome wastes most of its informational potential. For a distribution with entropy H, the theoretically minimum expected number of yes/no questions to identify the outcome is H itself if the probabilities happen to be exact powers of 1/2, and it is provably impossible to do better than H on average for any distribution — that is the actual content of Shannon's source coding theorem, and no cleverness in how you phrase the questions can beat it.

Source coding: entropy is a promise a real code can nearly deliver

Given a source's entropy H, Shannon's source coding theorem guarantees that a code exists whose average length per symbol gets arbitrarily close to H bits (by coding long enough blocks of symbols at once), and that no lossless code can average below H. Practical prefix-free codes approach this bound directly:

Huffman coding    → optimal PREFIX-FREE code for known, fixed probabilities;
                     average length is within 1 bit of H, often much closer;
                     exactly matches H when every probability is a power of 1/2

Arithmetic coding → encodes the whole message as one fractional number;
                     not restricted to whole-bit-per-symbol codewords, so it
                     converges to H even when Huffman cannot get arbitrarily close

entropy H = 0.469 bits/symbol (90/10 biased coin, worked out above)
→ any lossless compressor on that source is mathematically guaranteed
  to need at least 0.469 bits per symbol on average — no exceptions

This is why entropy is quoted as the theoretical compression floor: gzip, zstd, JPEG's entropy stage, and every general-purpose compressor are all, at their final stage, approximating an entropy coder against some estimated probability model of the data. A better probability model (accounting for context, correlations between symbols, etc.) lowers the effective entropy and therefore the achievable compressed size — but no model, however good, lets you beat the entropy of the true underlying distribution.

Beyond one symbol: joint, conditional, and cross entropy

Real sources are rarely independent symbol-by-symbol — English text has strong correlations between consecutive letters, for instance — and entropy generalises cleanly to handle this. Joint entropy H(X,Y) measures the uncertainty of a pair of variables together; conditional entropy H(Y|X) measures how much uncertainty remains in Y once X is already known, and it is always ≤ H(Y) — knowing something never increases your uncertainty about something else, on average. Cross entropy, H(p,q) = -Σ p(x)log2(q(x)), measures the average code length when you encode data from the true distribution p using a code optimised for a different, possibly wrong, estimated distribution q — and it is exactly the loss function minimised when training a classifier, because a lower cross-entropy loss means the model's predicted probabilities are closer to the true label distribution.

Frequently asked questions

Try it live

Everything above runs in your browser — open Shannon Entropy and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.