The source coding theorem

Flip a coin 1000 times, with heads probability 0.9. The sequence you obtain is almost certainly one with about 900 heads and 100 tails, so the sequences that actually occur form a tiny minority of the $2^{1000}$ possible strings. A code can ignore the rest and name only the sequences in that minority, and this is how a message becomes shorter than its symbols suggest.

How short can a long message be? The number of likely sequences is about $2^{469}$, not $2^{1000}$, so naming one of them takes about 469 bits rather than 1000. The saving comes from the shape of the distribution, not from any cleverness in the encoder. !Strings of 1000 flips of a coin whose common outcome has probability 0.9, counted by how many common outcomes they contain. The line at 1000 is the whole space of $2^{1000}$ strings. The curve is ${\log }_{2}C(1000,k)$: at k = 900 it is 464, and those strings are individually the likely ones, each with probability about $2^{-469}$. The shaded band carries almost all the probability, and the entropy scale puts the effective size of the typical set at about $2^{469}$ strings, not $2^{1000}$. Naming a string from that band takes about 469 bits rather than 1000. Status: synthetic.

The typical set. For a long sequence of independent symbols, the probability of the whole sequence is close to $2^{-mH}$, where H is the entropy of one symbol and m is the number of symbols [S:36:92]. Almost all of the probability sits on a small set of sequences, the typical set, and each member of that set has roughly the same probability. The set contains about $2^{mH}$ members, which is a vanishing fraction of all $2^m$ strings whenever H is below the logarithm of the alphabet size. !Bits per flip for Huffman codes on blocks of 1, 2, 4, 8, 12 and 16 flips of the 0.9 coin. One flip costs 1 bit, two cost 0.645 bits each, and four cost 0.493 each; by twelve flips the cost is 0.470, above the entropy floor of 0.469. At sixteen it ticks back up to 0.472, because Huffman redundancy is not monotone at finite block length. Longer blocks close the gap and cost memory and delay, because the code needs a probability for each of the $2^m$ blocks. Status: re-simulated.

The typical set earns its name from the law of large numbers, which says that an average over many independent draws settles near its expected value. As the sequence grows, the fraction of heads concentrates near its expected value, so the probability of the whole sequence concentrates near $2^{-mH}$ [S:36:92]. Sequences outside the set exist in huge numbers, but together they carry almost no probability.

When the source is far from uniform, the most probable single sequence is not typical. For the biased coin, the all-heads sequence has the highest probability of any one sequence, yet its information per symbol is ${\log }_2(1/0.9)$, far from the entropy, so it sits outside the typical set [S:36:88]. The typical set is made of individually less probable sequences that together carry almost all the probability [S:36:92].

The theorem. Shannon's source coding theorem is the result that long blocks can be compressed to about their entropy in bits, and no further without loss. For a long block of independent symbols with entropy H, you can compress them into slightly more than $mH$ bits with negligible risk of loss, as the block grows. Compress into fewer than $mH$ bits, and information is almost certain to be lost [S:36:93].

For a single symbol, the theorem has a simpler form. There is a prefix code whose average length L satisfies

$$H\le L<H+1$$

The equation says that entropy is a floor no lossless code can cross, and that a good code stays within one bit of it [S:36:110].

The converse is a counting argument. A block of m symbols has about $2^{mH}$ typical sequences, and a code with fewer than $mH$ bits has fewer than $2^{mH}$ codewords. Two typical sequences must therefore share a codeword, so at least one of them cannot be recovered. No clever encoder escapes this count, because the count is what the typical set is.

Worked example. Return to the coin with heads probability 0.9, whose entropy is 0.469 bits per flip. A fixed code for one flip needs 1 bit, and a block code for two flips, which encodes two symbols at once, has four sequences with probabilities 0.81, 0.09, 0.09 and 0.01. Huffman gives lengths 1, 2, 3 and 3, so the average is $0.81+2(0.09)+3(0.01)+3(0.09)=1.29$ bits per pair, or 0.645 bits per flip.

For four flips the average falls to 1.9702 bits per block, or 0.493 bits per flip, and the floor is 0.469. Longer blocks keep closing the gap, which is why the theorem talks about a limit rather than a single code. The approach is steady but slow, and the next paragraph explains what it costs.

The improvement has a price. A block of twenty flips has about a million possible sequences, so the encoder needs probabilities for all of them, and the decoder must wait for the whole block before it can emit the first symbol. Longer blocks close the gap to entropy more tightly and cost more memory and delay.

The theorem is a promise about long blocks. It assumes independent symbols and a known distribution, and it says nothing about short messages, where rounding and headers can cost more than the saving. Real text has memory: the next letter depends on the ones before it, so a model of that memory is needed before the floor can be approached. That is why compression and modelling are the same job [S:36:150].

The formal statement. Let $X_1,\dots ,X_N$ be independent draws from a finite alphabet with entropy H. Write $H_{\delta }(X^N)$ for the logarithm of the smallest number of strings that carry probability at least $1-\delta$. Fix an $ϵ>0$ and a $0<\delta <1$. Then there is an $N_0$ such that for all $N>N_0$,

$$\frac{1}{N}{H}_{\delta }(X^N)-H<ϵ.$$

The equation says that a set of about $2^{NH}$ strings carries almost all the probability, so N symbols need about $NH$ bits and no fewer [S:36:90].

The derivation. Define the surprise per symbol of a string x as $(1/N){\log }_{2}1/P(x)$. This is the average of N independent terms, each with mean H and finite variance. The weak law of large numbers says that for any $\beta >0$ the probability that this average lies within $\beta$ of H tends to one. Call those strings typical.

Every typical string has probability between $2^{-N(H+\beta )}$ and $2^{-N(H-\beta )}$. The typical set cannot have more than $2^{N(H+\beta )}$ members, because its total probability is at most one. Name each member with $N(H+\beta )$ bits, and add one flag bit for the atypical strings. The flag costs one bit and the atypical set has probability at most $\delta$. That gives compression to $N(H+ϵ)$ bits with error at most $\delta$.

The converse is the same count in reverse. For any set S of M strings, $P(S)\le P(S\cap T_{N\beta })+P(S\cap T_{N\beta }^c)\le M{2}^{-N(H-\beta )}+\delta$, because every typical string has probability at most $2^{-N(H-\beta )}$ and the atypical set has probability at most $\delta$. Taking $\beta <ϵ$ shows that a set with fewer than about $2^{N(H-ϵ)}$ members cannot carry probability near one, and if two typical strings share a name, one of them is lost [S:36:92] [S:36:93].

The edge case. When the source is far from uniform, the most probable string has probability far above $2^{-NH}$ and lies outside the typical set [S:36:92]. For the biased coin, the all-heads string is the single most probable string, yet the strings inside the typical set carry almost all the probability. For a uniform source every string is typical, so no such exclusion holds. A code that spends its shortest names on the top of the probability ranking therefore loses on the block average. L1's phrase "name the likely sequences" invites this mistake; the theorem names a set, not a favourite string.

What L1 hid, and why that was safe. L1 suppressed the two small parameters. The flag bit and the atypical set are what the $ϵ$ and $\delta$ pay for, and both vanish per symbol as N grows. L1 also omitted the requirement that the encoder know the distribution, because its coin was given. The block code of twenty flips in L1 shows the cost that remains at finite N: the theorem promises a limit, not a small code.

Where the analogy breaks. The list of typical strings is not a fixed dictionary. It depends on the model, and a wrong model produces a short list that misses the string you actually send. That is why an arithmetic coder carries the model with it rather than a fixed table.

Original sources. Shannon proves that a source of entropy H can be sent over a channel of capacity C whenever H is below C, and that no coding beats that limit [S:156:16]. His second proof builds the code from cumulative probabilities and bounds the excess by the difference between the true entropy and the entropy of the block model. MacKay states the block version with the two small parameters and proves it from the typical set [S:36:90]. Polyanskiy and Wu give the modern form, including the normal approximation with varentropy [S:34:239].

An open question. Shannon's floor is an average over an ensemble. For one finite string, the shortest description is the Kolmogorov complexity, and that function is not computable [S:39:14]. So the question "how short can this message be" has no algorithmic answer in general. A compressor with a proved redundancy bound settles it for a restricted class, which is what Lempel-Ziv does for ergodic sources [S:34:236]. A class without such a bound leaves the question open for that class.

A frontier result. The finite-blocklength refinement adds a term proportional to the square root of the blocklength times the varentropy, so the price of a finite block becomes explicit [S:34:239]. The refinement depends on the source coding theorem for its centre and on a variance calculation for its width.

The second proof. Shannon's first proof counts typical sequences. The second proof is constructive: it expands the cumulative probability of each message in binary and truncates at a length slightly above the information content [S:156:17]. That construction is the ancestor of the arithmetic coder of Section 16.4, and it shows that the bound is not only an existence result.

What to read next. Read Shannon's Part I for the original proof [S:156:16]. Read MacKay 4.4 and 4.5 for typicality and the counting argument [S:36:92]. Read Polyanskiy Chapter 11 for the finite-blocklength statement [S:34:239]. Read the preface of Shen, Uspensky and Vereshchagin for the shift from an ensemble to a single string [S:37:5]. The four together mark the boundary of what the theorem promises.