Source coding theorem
Compression has a floor and the floor is entropy. Shannon's theorem (MacKay's Theorem 4.1): for
an ensemble X with entropy H, given any ε > 0 and 0 < δ < 1, there is an N₀ such that for
all N > N₀ the essential bit content per symbol of N independent draws is within ε of H.
The verbal form is easier to hold onto:
"
Ni.i.d. random variables each with entropyH(X)can be compressed into more thanNH(X)bits with negligible risk of information loss, asN → ∞; conversely if they are compressed into fewer thanNH(X)bits it is virtually certain that information will be lost."
Sourced from information-theory-inference-learning-algorithms, held in ../machine-learning-wiki
(see the provenance note on information-theory).
The shape of the proof
Name every member of the typical set. There are about 2^{NH} of them, so NH bits of names
suffice, and the probability that a draw falls outside the set goes to zero. The converse is the same
count from the other side: fewer than NH bits cannot address that many sequences, so something gets
lost. The tolerance δ for error barely matters — allow a large error probability and you still
cannot compress below NH, which is what makes the floor a floor rather than a trade-off.
Underneath it is Chebyshev's inequality and the law of large numbers from probability-theory,
applied to the random variable log 1/P(x).
Symbol codes: the price of not waiting for infinity
The theorem is asymptotic; a symbol code assigns a codeword to each symbol separately and pays for it. The two results that bound it:
- Kraft inequality — a uniquely decodable code's lengths must satisfy
Σᵢ 2^{−lᵢ} ≤ 1, and conversely any lengths satisfying it admit a prefix code. So the question "which codeword lengths are achievable" has a complete answer independent of any construction. - Theorem 5.1 — there is a prefix code with expected length
LsatisfyingH(X) ≤ L < H(X) + 1. The one-bit slack is the cost of roundinglog₂(1/pᵢ)up to an integer.
Huffman coding (1952) achieves the optimum by a two-line construction: take the two least probable symbols, give them codewords of equal length differing in the last digit, merge them into one symbol, repeat. It is optimal among symbol codes and still up to one bit per symbol away from the entropy — expensive when the alphabet is small and skewed, since the excess is per symbol.
Stream codes: modelling is the compression
Chapter 6 breaks the one-codeword-per-symbol constraint, and MacKay uses it to make the argument the book is really about.
Arithmetic coding encodes an entire message as one interval, driven by a probabilistic model of the source supplied separately. Better model, shorter output, no rounding loss per symbol. There is no general-purpose arithmetic coder; a model has to be written for each kind of source, which MacKay treats as the honest situation rather than a defect.
Lempel–Ziv takes the opposite philosophy: no model at all, just a dictionary of substrings seen so far. It is provably universal — for any ergodic source it compresses asymptotically to the entropy — and MacKay is blunt about what the proof is worth in practice: the asymptotic timescale "may, for many sources, be unfeasibly long," because the number of typical substrings to memorise can be enormous. Its real-world usefulness comes from files repeating short strings, not from the universality theorem. On English text it "does not match the standards set in the arithmetic coding literature."
The two philosophies converge in principle — one could build adaptive universal models for arithmetic coding — and MacKay names the limit of that idea in a sentence written in 1999:
"A general purpose compressor that can discover the probability distribution of any source would be a general purpose artificial intelligence! A general purpose artificial intelligence does not yet exist."
Where this is used across the hub
../llm-inference-wikiand../machine-learning-wiki— the compression-is-prediction identity descends directly from this chapter, and so does the modern claim that a language model is a compressor. The derivation lives with information-theory-inference-learning-algorithms.../dev-tooling-wiki— the serialization formats there consume this theory and never state it.
Related
information-theory · entropy · noisy-channel-coding-theorem · probability-theory · claude-shannon · information-theory-inference-learning-algorithms · mathematics · synthesis