Symptom

You gzip a log file and it drops to 8% of its original size. You gzip the already-gzipped file and it gets slightly bigger. Somebody asks why, and the honest answer you have is “because it’s already compressed,” which is a restatement, not a reason.

Or: you are choosing a compression level, and you want to know when to stop paying for CPU. Level 9 buys you 2% over level 6. Would level 22 buy another 2%? Is there a number that says where the floor is?

Or the one from a design review: someone proposes storing a million UUIDs and compressing them. Somebody else says it will not help. Both are guessing.

T004 told you no compressor shrinks everything. It did not tell you how far a compressor can go on the data you actually have. There is an exact number, it is computable from the data, and it was defined in 1948.

Statement

For a source emitting symbols from an alphabet with probabilities $p_i$, the entropy is

$$H = -\sum_i p_i \log_2 p_i \quad\text{bits per symbol}$$

Source coding theorem. For a source of entropy $H$, and any $\varepsilon > 0$, there is a lossless code with average length $< H + \varepsilon$ bits per symbol. And no lossless code achieves average length $< H$.

Both halves matter and they are usually quoted separately. The second half is the impossibility: $H$ is a floor nothing gets under. The first is the achievability: the floor is reachable, not merely a bound someone proved. It is rare for a lower bound to be tight, and this one is.

Read $-\log_2 p_i$ as the “surprise” of symbol $i$: a symbol with probability $1/8$ carries 3 bits. Entropy is then just the average surprise, and the theorem says average surprise is exactly the cost of writing the data down.

Argument

The floor. Suppose a prefix-free code assigns length $\ell_i$ to symbol $i$. Kraft’s inequality says any prefix-free code satisfies $\sum_i 2^{-\ell_i} \le 1$ — which is a counting fact, not an assumption: reserving a codeword of length $\ell$ removes a $2^{-\ell}$ fraction of the space of possible continuations, and you cannot spend more than all of it.

Now compare the average length $L = \sum_i p_i \ell_i$ against $H$:

$$L - H = \sum_i p_i \ell_i + \sum_i p_i \log_2 p_i = \sum_i p_i \log_2 \frac{p_i}{2^{-\ell_i}}$$

That last quantity is a relative entropy (a Kullback–Leibler divergence) between the distribution $p$ and the sub-distribution $q_i = 2^{-\ell_i}$, and it is never negative. The one-line reason is Jensen’s inequality applied to the concave $\log$:

$$-\sum_i p_i \log_2 \frac{q_i}{p_i} \;\ge\; -\log_2 \sum_i p_i \frac{q_i}{p_i} = -\log_2 \sum_i q_i \;\ge\; -\log_2 1 = 0$$

So $L \ge H$, with equality exactly when $\ell_i = -\log_2 p_i$ for every $i$. $\blacksquare$

The ceiling. Set $\ell_i = \lceil -\log_2 p_i \rceil$. These satisfy Kraft, so such a code exists (Shannon–Fano), and since each length overshoots by less than 1,

$$L < \sum_i p_i (-\log_2 p_i + 1) = H + 1$$

That gives $H + 1$, not $H + \varepsilon$. To close the gap, encode blocks of $n$ symbols at a time. The overhead of at most 1 bit is now spread over $n$ symbols, so the per-symbol cost is below $H + 1/n$, and $n$ can be as large as you like. That blocking step is the whole content of “$\varepsilon$”, and it is also why real compressors work on streams rather than symbol by symbol.

A worked example, since the formula is opaque until you use it. English text, treated as 26 letters plus space with their actual frequencies, has $H \approx 4.1$ bits per character — against the $\log_2 27 \approx 4.75$ bits a uniform code would need. But letters are not independent: q is followed by u, th is common. Taking that structure into account, Shannon estimated English at about 1.0 to 1.5 bits per character. A naive ASCII file spends 8. That factor of six is exactly the room gzip is exploiting, and it is why text compresses well and why nothing compresses text below about 1 bit per character.

Two sanity checks on the formula:

  • A fair coin. $p = (1/2, 1/2)$, so $H = -2 \times \tfrac12 \log_2 \tfrac12 = 1$ bit. One bit per flip, which is right, and unimprovable.
  • A biased coin at $p = 0.99$. $H = -0.99\log_2 0.99 - 0.01\log_2 0.01 \approx 0.08$ bits. A sequence of 1000 such flips needs about 80 bits, not 1000. This is the compression the intuition misses.

Forbids

Compressing uniform random data. $n$ uniform random bits have $H = n$. No code stores them in fewer than $n$ bits on average. This is why the compressed file will not compress again: a good compressor’s output is nearly uniform by construction, so it has already spent its slack.

Compressing a million UUIDs. Each carries 122 random bits, so a million of them hold $1.22 \times 10^8$ bits $\approx 15$ MB, and no encoding does better. (The textual form with its dashes and hex is 36 bytes, so there is a 2.4$\times$ win available from parsing them into bytes — but that is removing encoding overhead, not compressing entropy.)

Beating $H$ by being clever about the algorithm. The bound does not care what your algorithm is. Arithmetic coding, ANS, Huffman, a neural net: they differ in how close to $H$ they get and how fast, never in whether they can go under.

A meaningful “compression ratio” claim without naming the source. Ratios are properties of a source-and-compressor pair. “Our algorithm achieves 10:1” is only a claim about the test data’s entropy until proven otherwise.

Does not forbid

It does not say your file cannot be compressed below its current entropy estimate, and this misreading gets used to shut down real work. Entropy is defined relative to a model of the source. Measure a file’s byte histogram, get 7.9 bits per byte, and conclude it is incompressible — and then a context-mixing compressor finds structure the histogram could not see and halves it. This happens routinely; it is most of what the Hutter Prize is about. The order-0 entropy is a floor for order-0 models only. Every improvement in compression since 1948 has come from better models, not from beating Shannon, and the theorem specifically leaves that door open.

It does not forbid lossy compression from doing far better. JPEG, MP3, and H.264 achieve ratios that would be impossible losslessly, because they are answering a different question — how few bits to reproduce something a human cannot distinguish. That is rate–distortion theory, also Shannon’s, with its own and much lower floor. When someone says “you can’t compress video that much,” they are quoting the wrong theorem.

It does not mean an individual string has an entropy. This is a genuine technical confusion worth naming. $H$ is a property of a distribution, not of a string. The string 0000000000 has no entropy; the source that emitted it does. The per-string analogue is Kolmogorov complexity — the length of the shortest program producing it — which is uncomputable, and which is the subject of its own post. Asking “what is the entropy of this file” is a type error that everyone commits, including this post’s opening section, and it is usually harmless as long as you know it is shorthand for “of the model I fitted to it.”

It does not mean compressed data is random. Compressed output is statistically close to uniform, which is exactly why it resists further compression, and it is completely predictable to anyone holding the decompressor. Encryption is not compression, and using gzip output as a source of entropy for a key is a real mistake people have made.

It does not forbid a specific file from shrinking a lot. The floor is on average length over the source distribution. A particular low-probability-looking file may compress magnificently. Averages bind the long run, not any single case, which is the same distinction T001 draws between existence and likelihood.

Boundary

  • Better models. The most productive direction, and where essentially all practical progress lives. Order-0 entropy assumes independent symbols; conditioning on context lowers $H$, sometimes dramatically. LZ77 exploits repetition, PPM and context mixing predict from history, and modern neural compressors are simply very good models paired with an arithmetic coder. Each is a tighter estimate of the true source entropy, not a violation of it.
  • The gap between $H$ and $H+1$. Huffman coding is optimal among symbol-wise codes but can waste up to 1 bit per symbol, which is catastrophic when $H$ is small — a symbol of probability 0.99 still costs a whole bit. Arithmetic coding and ANS remove this by not requiring integer code lengths, which is why they replaced Huffman where the alphabet is skewed.
  • Universal codes. Lempel–Ziv achieves the entropy rate without knowing the source distribution in advance, asymptotically. That is a remarkable result and the reason gzip needs no training pass over your data.
  • Kolmogorov complexity. Drop the probabilistic source and ask for the shortest program that outputs a specific string. This is the strongest form of the question, it agrees with entropy on average, and it is uncomputable — which is a considerably worse boundary than the one Shannon drew, and gets its own post.
  • Channels, not just sources. The other half of Shannon’s 1948 paper turns the question around: given a noisy channel, how much can you reliably send? The channel coding theorem says up to the channel capacity, with arbitrarily low error, which is at least as surprising as this result and is what makes error-correcting codes possible.