Notes on Coding Theory

Notes that start with assigning bits to symbols, then build toward context models, Markov codes, and Kolmogorov complexity.

0. How we arrive at the coding problem

Starting point: represent a stream of symbols (letters, pixels, sensor readings) as a sequence of bits, for storage or transmission.

Naive approach: give every symbol a fixed number of bits (8 bits for a byte, or $\lceil \log_2 N \rceil$ bits for $N$ possible symbols). This is what ASCII does: it treats all symbols as equally likely. Real sources are not uniform: in English text, "e" occurs with frequency around 0.127, "z" around 0.001.

If the probability distribution of symbols is known, fewer bits can be spent on frequent symbols and more on rare ones. Frequent symbols repeat often in a message, so this trade reduces the total/average message length, even though rare symbols individually get longer codewords.

The quantity $-\log_2 p(x)$ answers how many bits should be paid for that surprise.

Questions this raises:

What is the formal setup, and what does the probability of a symbol have to do with bits? Section 1.
What quantity is minimized? Section 2.
If codewords have variable length, how is decoding ambiguity avoided? Section 3 (prefix-free codes).
How is an optimal prefix-free code constructed? Section 4 (Huffman coding).
Can symbol-by-symbol encoding be avoided altogether? Section 5 (arithmetic coding).
What formal bound governs all of this, and what is left out of sections 1 to 5? Sections 6 to 13.
How do dependencies change the coding problem, and how can the code learn them? Sections 14 to 16 (conditional entropy and Markov codes).
What does it cost to describe the model, and what if any program could be a description? Sections 17 to 20 (two-part codes and Kolmogorov complexity).

1. Codes, lengths, and information content

Fix a finite alphabet $\mathcal{X} = {x_1, \ldots, x_n}$ and a probability mass function $p$ on it with $p(x) > 0$ for every $x$ , so $n = |\operatorname{supp} p|$ . The source emits $X_1, X_2, \ldots$ drawn i.i.d. from $p$ (Sections 9 and 10 drop the independence assumption).

A binary code is a map $C : \mathcal{X} \to {0,1}^*$ , with length function $L(x) = |C(x)|$ . It is uniquely decodable if every finite sequence of codewords can be decoded in exactly one way, without ambiguity. Prefix-free codes are a special case: no codeword is a prefix of another, so decoding can be done left-to-right with no lookahead. Two results from Sections 3 and 8, used here in advance:

every uniquely decodable code satisfies the Kraft inequality $\sum_x 2^{-L(x)} \le 1$
every $L : \mathcal{X} \to \mathbb{N}$ satisfying that inequality is the length function of some prefix-free code

So a code may be identified with its length function, and the admissible set is exactly

$\mathcal{L} = \Big\lbrace L : \mathcal{X} \to \mathbb{N} \Big| \sum_{x \in \mathcal{X}} 2^{-L(x)} \le 1 \Big\rbrace$

The number of codewords, meaning the size of the image $C(\mathcal{X})$ , is not a design variable: it is $n$ , fixed by the support of $p$ , since every symbol needs exactly one codeword and distinct symbols need distinct ones. The only freedom is how the $n$ lengths are chosen inside $\mathcal{L}$ , and the constraint is what makes the choice non-trivial, as shortening one codeword forces another to lengthen.

Information content. For $x \in \mathcal{X}$ , define

$h_p(x) = -\log_2 p(x) \in (0, \infty)$

the information content (or surprisal) of $x$ under $p$ , measured in bits. Three properties:

negative monotone on $p(x)$ : rarer symbols have larger $h_p$
halving $p(x)$ adds exactly one bit, so $h_p$ is the number of halvings of the probability scale needed to reach $p(x)$ : a length- $\ell$ codeword occupies a $2^{-\ell}$ share of the code tree, matching probability $2^{-\ell}$
additive on independent draws: if $X \sim p$ and $Y \sim p'$ are independent, the information content of the pair $(x, y)$ under the joint law is $h_p(x) + h_{p'}(y)$ , matching concatenation of codewords, which adds lengths

Note that $h_p$ is a function of the pair $(x, p)$ , not of $x$ alone, and that it is a real number, generally not an integer length. The claim that it is the ideal length is a statement about the whole function $L$ relative to an objective (Section 2 proves this).

Running example, carried through Section 5: $\mathcal{X} = {A, B, C, D}$ with

Symbol	$p(x)$	$h_p(x) = -\log_2 p(x)$
A	1/2	1 bit
B	1/4	2 bits
C	1/8	3 bits
D	1/8	3 bits

This $p$ is dyadic, meaning every $p(x)$ is a power of $1/2$ , so here $h_p$ happens to be integer-valued and therefore realizable exactly. That is special: Section 3 takes up the general case.

Reading the example as a tree. Circles and pill-shaped nodes are internal nodes, square boxes are symbols, edge labels are the bit (or symbol) taken on that branch. Every split halves the mass, so a symbol's depth equals $h_p(x)$ :

flowchart TD
    R(["1"]) --> A["A<br/>p = 1/2<br/>depth 1"]
    R --> N1(["1/2"])
    N1 --> B["B<br/>p = 1/4<br/>depth 2"]
    N1 --> N2(["1/4"])
    N2 --> C["C<br/>p = 1/8<br/>depth 3"]
    N2 --> D["D<br/>p = 1/8<br/>depth 3"]

2. What are we actually minimizing?

Three scalar summaries could be used to evaluate a length function $L \in \mathcal{L}$ :

worst case, $\max_x L(x)$
unweighted average over the codebook, $\frac{1}{n}\sum_x L(x)$
source-weighted average, $E_p[L(X)] = \sum_x p(x) L(x)$

Neither of the first two involves $p$ , so both reproduce the naive approach of Section 0. Objective 1 is minimized by the fixed-length assignment $L \equiv \lceil \log_2 n \rceil$ , since Kraft forces some codeword to have length at least $\log_2 n$ . Objective 2 is literally objective 3 with $p$ replaced by the uniform distribution $u$ , so by Theorem 2.1 below its relaxed optimum is the flat $L \equiv \log_2 n$ : adopting it amounts to assuming the source is uniform.

Objective 3 is the one that counts bits actually spent. Encoding $m$ symbols costs $\sum_{i=1}^{m} L(X_i)$ bits, whose expectation is $m E_p[L(X)]$ and whose per-symbol average converges to $E_p[L(X)]$ almost surely. So $E_p[L]$ is the bit rate of the code, in bits per symbol, and the design problem is

$\min_{L \in \mathcal{L}} E_p[L(X)]$

Relaxation. Solve it first over real-valued lengths, dropping integrality but keeping Kraft:

$\mathcal{L}_{\mathbb{R}} = \Big\lbrace L : \mathcal{X} \to \mathbb{R} \Big| \sum_x 2^{-L(x)} \le 1 \Big\rbrace \supset \mathcal{L}$

Theorem 2.1. $E_p[L(X)]$ attains its minimum over $\mathcal{L}_{\mathbb{R}}$ uniquely at $L^\star(x) = h_p(x) = -\log_2 p(x)$ , with optimal value $\sum_x p(x) \log_2 \tfrac{1}{p(x)}$ (named in Section 7).

Proof. Write $q(x) = 2^{-L(x)}$ , the leaf space of $x$ (Section 3). Kraft says $\sum_x q(x) \le 1$ , and the objective becomes the cross entropy

$E_p[L(X)] = H(p, q) = -\sum_x p(x) \log_2 q(x)$

With $\ln s \le s - 1$ (the tangent line at $s = 1$ ) at $s = q(x)/p(x)$ ,

$H(p, q) - H(p, p) = -\sum_x p(x) \log_2 \frac{q(x)}{p(x)} \ge (\log_2 e) \sum_x p(x)\Big(1 - \frac{q(x)}{p(x)}\Big) = (\log_2 e)\Big(1 - \sum_x q(x)\Big) \ge 0$

Equality needs $q = p$ pointwise (the tangent touches only at $s = 1$ ) and $\sum_x q(x) = 1$ , so the minimum is attained only at $L^\star = -\log_2 p$ . $\square$

Why $-\log_2 p$ . Shortening the codeword of $x$ by $\delta$ saves $p(x)\delta$ bits of rate and costs $(\ln 2) 2^{-L(x)} \delta$ of leaf space. If the saving per unit of leaf space differed between two symbols, moving space between them would lower the rate, so at the optimum $2^{-L(x)} \propto p(x)$ . All leaf space is used, so the constant is 1.

Two consequences.

Corollary 2.2 (mismatch). A code built from a model $q$ rather than from the true $p$ has lengths $-\log_2 q(x)$ and rate $E_p[-\log_2 q(X)] = H(p, q) \ge H(p, p)$ .

This is the best we can do if we only have a proxy distribution $q$ for the true source $p$ . The excess bits $E_p[-\log_2 q(X)] - E_p[-\log_2 p(X)]$ are introduced in the next corollary and precisely bounded in Section 7. Shrinking them is what Sections 9 to 11 are for.

Corollary 2.3 (saving over fixed length). Since the fixed-length code is Theorem 2.1 applied to $u$ , its excess rate under the true source is

$E_p[\log_2 n] - E_p[L^\star] = \log_2 n - \sum_x p(x)\log_2\tfrac{1}{p(x)} = D(p | u)$

the relative entropy to the uniform distribution (Section 7). The available saving is exactly how far $p$ is from uniform. Compression exploits skew in $p$ , irrespective of the size of the alphabet.

Example continued. For $p = (1/2, 1/4, 1/8, 1/8)$ the optimum is $L^\star = (1, 2, 3, 3)$ , which is integral, hence in $\mathcal{L}$ , hence achievable: the code A=0, B=10, C=110, D=111 constructed in Section 4 realizes it.

$E_p[L^\star] = \tfrac12(1) + \tfrac14(2) + \tfrac18(3) + \tfrac18(3) = 1.75 \text{ bits/symbol}$

against $\log_2 4 = 2$ for fixed length: 1750 bits versus 2000 bits per 1000 symbols, a saving of $D(p | u) = 0.25$ bits/symbol. As trees, $E_p[L]$ is the probability-weighted average leaf depth. The fixed-length code is balanced, every leaf at depth 2 regardless of probability. The optimal tree is deliberately lopsided: the heavy leaf A is pulled up to depth 1, the light leaves C and D pushed down to depth 3.

Fixed-length code, $E_p[L] = 2$ bits/symbol:

flowchart TD
    F0((" ")) -->|0| F1((" "))
    F0 -->|1| F2((" "))
    F1 -->|0| FA["A = 00<br/>p = 1/2"]
    F1 -->|1| FB["B = 01<br/>p = 1/4"]
    F2 -->|0| FC["C = 10<br/>p = 1/8"]
    F2 -->|1| FD["D = 11<br/>p = 1/8"]

Optimal code, $E_p[L] = 1.75$ bits/symbol:

flowchart TD
    V0((" ")) -->|0| VA["A = 0<br/>p = 1/2"]
    V0 -->|1| V1((" "))
    V1 -->|0| VB["B = 10<br/>p = 1/4"]
    V1 -->|1| V2((" "))
    V2 -->|0| VC["C = 110<br/>p = 1/8"]
    V2 -->|1| VD["D = 111<br/>p = 1/8"]

The relaxation works only when $L^\star$ lies in $\mathcal{L}$ , which happens only for dyadic $p$ . In general the integrality dropped above costs something (Section 3), the best integer solution has to be constructed (Section 4, Huffman), and this cost can be avoided altogether by coding whole sequences instead of symbols (Section 5, arithmetic coding).

3. Prefix-free codes and the Kraft inequality

Definition: no codeword is a prefix of another codeword. Equivalent to: every codeword is a leaf on a binary tree.

This property allows unambiguous, immediate left-to-right decoding with no lookahead and no separators.

Not prefix-free:

A = 0
B = 01

Reading 0: this could be A, or the start of B. Ambiguous without extra rules.

In the tree, A sits on an internal node with B below it. After reading 0 the decoder has reached a codeword but cannot stop there, because the path may continue to B:

flowchart TD
    R((" ")) -->|0| A["A = 0<br/>on an internal node"]
    A -->|1| B["B = 01"]
    class A bad
    classDef bad fill:#fde2e2,stroke:#c62828,color:#000

Prefix-free:

A = 0
B = 10
C = 110
D = 111

Bitstream 01101110 decodes uniquely as 0 | 110 | 111 | 0, that is A C D A.

Decoding is a walk on the code tree (the optimal-code tree in Section 2): start at the root, follow one edge per bit, emit the symbol on reaching a leaf, then jump back to the root. Trace for 01101110:

Bits consumed	Path from root	Leaf	Output so far
`0`	0	A	A
`110`	1, 1, 0	C	A C
`111`	1, 1, 1	D	A C D
`0`	0	A	A C D A

At no point does the decoder look at a bit beyond the leaf it is on.

Guarantee mechanism, binary code tree:

Left branch = 0, right branch = 1
Symbols occupy only leaves
A leaf has no children, so no other codeword can extend past it, so the code is automatically prefix-free

Kraft inequality: necessary and sufficient condition for a valid prefix-free binary code with lengths $L(x)$ :

$\sum_x 2^{-L(x)} \le 1$

A length- $n$ codeword consumes a $2^{-n}$ fraction of the tree's leaf space. Total consumption cannot exceed 1.

Leaf-space picture for A=0, B=10, C=110, D=111. Extend the tree to depth 3, which has 8 slots. A codeword at depth $n$ blocks all $2^{3-n}$ slots beneath it, since no other codeword may extend it. The blocked slots (dashed) together with C and D fill all 8, so the Kraft sum is exactly $4/8 + 2/8 + 1/8 + 1/8 = 1$ and no space is unused:

flowchart TD
    R((" ")) -->|0| A["A = 0<br/>blocks 4/8"]
    R -->|1| N1((" "))
    N1 -->|0| B["B = 10<br/>blocks 2/8"]
    N1 -->|1| N2((" "))
    N2 -->|0| C["C = 110<br/>1/8"]
    N2 -->|1| D["D = 111<br/>1/8"]
    A -.-|0| g00((" "))
    A -.-|1| g01((" "))
    g00 -.-|0| s000["000"]
    g00 -.-|1| s001["001"]
    g01 -.-|0| s010["010"]
    g01 -.-|1| s011["011"]
    B -.-|0| s100["100"]
    B -.-|1| s101["101"]
    class g00,g01,s000,s001,s010,s011,s100,s101 ghost
    classDef ghost fill:#f2f2f2,stroke:#9e9e9e,stroke-dasharray:4 3,color:#666

There are two ways the sum can differ from 1. Let's consider now the symbols A, B, C with lengths ${1, 2, 3}$ , this gives $1/2 + 1/4 + 1/8 = 7/8 < 1$ : a valid code, but the leaf 111 is wasted (C could be shortened to 11). Lengths ${1, 1, 2}$ give $1/2 + 1/2 + 1/4 = 5/4 > 1$ : once A and B take both depth-1 nodes, nothing is left for C. Lengths ${1, 2, 2}$ are valid and choosing between ${1, 2, 3}$ and ${1, 2, 2}$ depends on $p$ .

Cost of prefix-freeness: codeword lengths must be integers, but ideal lengths $-\log_2 p(x)$ are usually fractional. This mismatch produces overhead.

Example: $p(A)=0.7, p(B)=0.2, p(C)=0.1$

Ideal lengths: 0.51, 2.32, 3.32 bits (fractional, not realizable directly)
Actual code (Lengths ${1, 2, 2} \implies$ code A=0, B=10, C=11): average = 1.3 bits/symbol
Entropy $H(X) \approx 1.157$ bits/symbol
Overhead: 1.3 - 1.157 = 0.143 bits/symbol

Overhead at each leaf:

flowchart TD
    R((" ")) -->|0| A["A = 0<br/>p = 0.7<br/>ideal 0.51<br/>actual 1"]
    R -->|1| N((" "))
    N -->|0| B["B = 10<br/>p = 0.2<br/>ideal 2.32<br/>actual 2"]
    N -->|1| C["C = 11<br/>p = 0.1<br/>ideal 3.32<br/>actual 2"]

Rounding does not only go up. A is lengthened by about 0.49 bits, while B and C end up shorter than their ideal lengths (by 0.32 and 1.32 bits). The net overhead is positive because A occurs 70% of the time: $0.7(0.485) - 0.2(0.322) - 0.1(1.322) \approx 0.143$ .

Up until now, we have reasoned about optimal integer-length codes by manually enumerating all prefix-free codes. Next section presents a systematic algorithm to construct the best one.

4. Huffman coding, the best integer-length code

Greedy algorithm: repeatedly merge the two lowest-probability nodes into a combined node until one root remains. Codeword equals path from root.

Example (A=0.5, B=0.25, C=0.125, D=0.125):

Merge C+D to 0.25
Merge B+(CD) to 0.5
Merge A+(BCD) to 1.0

Resulting code: A=0, B=10, C=110, D=111.

Tree view. Internal nodes are labeled with the merge step that created them and their combined probability. Convention: at each merge the higher-probability child gets 0 (on a tie, the single symbol first). Any consistent choice works, since it changes the bit labels but not the lengths.

flowchart TD
    M3(["step 3<br/>1.0"]) -->|0| A["A = 0<br/>0.5"]
    M3 -->|1| M2(["step 2<br/>0.5"])
    M2 -->|0| B["B = 10<br/>0.25"]
    M2 -->|1| M1(["step 1<br/>0.25"])
    M1 -->|0| C["C = 110<br/>0.125"]
    M1 -->|1| D["D = 111<br/>0.125"]

A non-dyadic example with five symbols: A=0.35, B=0.25, C=0.20, D=0.12, E=0.08. Queue contents at each step, in ascending order:

Step	Queue before merging	Merge	New node
1	E 0.08, D 0.12, C 0.20, B 0.25, A 0.35	D + E	DE 0.20
2	C 0.20, DE 0.20, B 0.25, A 0.35	C + DE	CDE 0.40
3	B 0.25, A 0.35, CDE 0.40	A + B	AB 0.60
4	CDE 0.40, AB 0.60	AB + CDE	root 1.00

flowchart TD
    R(["step 4<br/>1.00"]) -->|0| AB(["step 3<br/>0.60"])
    R -->|1| CDE(["step 2<br/>0.40"])
    AB -->|0| A["A = 00<br/>0.35"]
    AB -->|1| B["B = 01<br/>0.25"]
    CDE -->|0| C["C = 10<br/>0.20"]
    CDE -->|1| DE(["step 1<br/>0.20"])
    DE -->|0| D["D = 110<br/>0.12"]
    DE -->|1| E["E = 111<br/>0.08"]

Resulting code: A=00, B=01, C=10, D=110, E=111. $E[L] = 2(0.35 + 0.25 + 0.20) + 3(0.12 + 0.08) = 2.2$ bits/symbol, against $H(X) \approx 2.153$ . Two differences from the first example. The final merge joins two merged subtrees (AB and CDE), so the tree is bushy rather than a single chain. And the lengths no longer equal the ideal lengths (1.51, 2.00, 2.32, 3.06, 3.64): for instance A gets 2 bits instead of about 1.5.

Running the algorithm on Section 3's distribution (0.7, 0.2, 0.1) merges B + C = 0.3, then A + (BC) = 1.0, which produces exactly the code A=0, B=10, C=11 used there.

Huffman coding is optimal among prefix-free, symbol-by-symbol codes.

Bound: $H(X) \le L_{\text{Huffman}} < H(X) + 1$

Limitation: codeword lengths per symbol remain integers. If one symbol has $p=0.9$ , ideal length is approximately 0.152 bits, but Huffman assigns it at least 1 bit. This inefficiency scales with how far the distribution is from powers of $1/2$ .

5. Arithmetic coding: how to spend fractional bits

Instead of a codeword per symbol, encode the whole message as one bit string, obtained from a shrinking sub-interval of $[0,1)$ .

From message to interval. Procedure:

Start with $[0,1)$ , partitioned according to symbol probabilities.
For each symbol observed, narrow the interval to that symbol's proportional sub-range.
Repeat, recursively subdividing within the current interval.
The final interval identifies the message. Its address in bits is constructed below.

Example: Symbols A=0.5, B=0.25, C=0.25. Initial partition of [0,1): A=[0,0.5), B=[0.5,0.75), C=[0.75,1). Message "AB":

Ingest A: Working interval = [0, 0.5)
Subdivide by the same proportions: A=[0, 0.25), B=[0.25, 0.375), C=[0.375, 0.5)
Ingest B. Final interval [0.25, 0.375), of width $0.125 = p(A) p(B)$

The line at each step, with the chosen sub-interval shaded. The third line cuts $[0,1)$ into the eight intervals named by 3-bit strings (next paragraph):

The subdivisions form a tree over messages rather than over symbols. Branches split in proportion to probability instead of in half, and each level adds one symbol. The width of a node's interval equals the probability of the message so far, here $p(\text{AB}) = 0.5 \times 0.25 = 0.125$ :

flowchart TD
    R["[0, 1)"] -->|A| A["A: [0, 0.5)<br/>width 0.5"]
    R -->|B| B["B: [0.5, 0.75)"]
    R -->|C| C["C: [0.75, 1)"]
    A -->|A| AA["AA: [0, 0.25)"]
    A -->|B| AB["AB: [0.25, 0.375)<br/>width 0.125"]
    A -->|C| AC["AC: [0.375, 0.5)"]
    class R,A,AB hit
    classDef hit fill:#e3f0fd,stroke:#1565c0,color:#000

Each step multiplies the width by the probability of the symbol ingested, so after $x_1, \ldots, x_n$ the width is

$w = \prod_{i=1}^{n} p(x_i) = p(x_1, \ldots, x_n)$

From interval to bits. A $k$ -bit string $b_1 \cdots b_k$ names the numbers whose binary expansion begins with those bits,

$[0.b_1 \cdots b_k, \ 0.b_1 \cdots b_k + 2^{-k})$

an interval of width $2^{-k}$ . For instance 010 names $[0.010_2, 0.010_2 + 2^{-3}) = [0.25, 0.375)$ . This is the leaf-space picture of Section 3 on the number line: a depth- $k$ node is an interval of width $2^{-k}$ , its children are its halves, and two strings are prefix-free exactly when their intervals are disjoint.

The encoder sends the shortest string whose interval lies inside the final interval $[l, l + w)$ . Fitting requires $2^{-k} \le w$ , so $k \ge -\log_2 w$ . Conversely $k = \lceil -\log_2 w \rceil + 1$ suffices, since then $2^{-k} \le w/2$ and an interval of width $w$ contains a whole grid cell of width $w/2$ or less wherever it sits. Together,

$-\log_2 w \le k < -\log_2 w + 2$

The bits sent are the information content of the message, $-\log_2 p(x_1, \ldots, x_n) = \sum_i h_p(x_i)$ , plus a constant below 2, paid once per message. The per-symbol overhead is below $2/n$ , against up to 1 bit for Huffman: rounding to an integer happens once, at the end, which is the gain.

Example continued. The final interval for "AB" $[0.25, 0.375)$ is exactly the interval of 010, so "AB" costs $3 = -\log_2 0.125$ bits. No constant is paid because $p$ is dyadic and the interval sits on the grid.

Skewed example. $p(A) = 0.9$ , $p(B) = 0.1$ , so $H(X) \approx 0.469$ bits/symbol, and the message is ten A's. Final interval $[0, 0.9^{10}) = [0, 0.349)$ , $-\log_2 0.349 \approx 1.52$ ideal bits. The 1-bit string 0 names $[0, 0.5)$ , which does not fit. The 2-bit string 00 names $[0, 0.25)$ , which does. Ten symbols cost 2 bits, against 10 bits for Huffman, which cannot give A fewer than 1 bit. Over long messages the rate approaches $H(X) \approx 0.469$ bits/symbol.

Decoding. The decoder computes $0.b_1 \cdots b_k$ , finds which sub-interval contains it, emits that symbol, rescales, and repeats. This works because the string's interval lies inside every sub-interval along the path. For 010: $0.25 \in [0, 0.5)$ , emit A. Inside $[0, 0.5)$ , $0.25 \in [0.25, 0.375)$ , emit B.

When to stop decoding. 00 also lies inside $[0, 0.9^{11})$ , so it is equally the code of eleven A's. The exact message interval would settle it (intervals of distinct messages never coincide), but its endpoints have no finite binary expansion in general, and the dyadic sub-interval that is sent loses the length. So either $n$ is transmitted up front, or an end-of-message symbol is added to the alphabet with its own probability. Even in the dyadic "AB" example, a termination convention is needed: a prefix-free code for individual symbols does not by itself delimit a message of arbitrary length.

For fixed $n$ the strings sent have disjoint intervals, so arithmetic coding is a prefix-free code over $\mathcal{X}^n$ and Section 3 applies to it. Unlike a Huffman tree, the message tree is never stored; encoder and decoder only compute the single path they need.

What is idealized. The final interval's endpoints are products of $n$ probabilities, and their expansions grow with $n$ . Section 11 shows how the encoder emits leading bits as soon as they are fixed and rescales the remainder in fixed-width integers. The bound above survives with a slightly larger constant.

6. Huffman or arithmetic?

Aspect	Huffman	Arithmetic
Unit of encoding	Per-symbol codeword	Entire sequence as interval/number
Codeword form	Explicit bit strings	Single number (interval)
Fractional bit lengths	Not possible per symbol	Effectively yes, amortized
Prefix-free tree	Yes, over symbols	Yes, over whole messages of length $n$ (never stored)
Bound relative to entropy	$H(X) \le L < H(X)+1$ per symbol	$H(X) \le L < H(X) + 2/n$ per symbol, for $n$ symbols
Implementation cost	Low	Higher (finite-precision arithmetic, see Section 11)

7. Shannon's source coding theorem (can't beat the entropy!)

Definition. The entropy of a random variable $X$ with distribution $p$ is the average information content of Section 1,

$H(X) = E_p[h_p(X)] = -\sum_x p(x) \log_2 p(x)$

in bits per symbol. It is also written $H(p)$ when the distribution is what matters. Theorem 2.1 says $H(X)$ is the minimum rate over real-valued length functions satisfying Kraft. The theorem below extends that floor to every uniquely decodable code.

Shannon's source coding theorem: for a source with entropy $H(X)$ , the average code length $L$ of any uniquely decodable code satisfies

$H(X) \le L$

and there exists a code (not necessarily achievable with integer lengths per symbol, but achievable in the limit by block coding or arithmetic coding) with

$$L < H(X) + 1$

Two consequences:

$H(X)$ is the hard floor for average code length, for any code, under any coding scheme, given the assumption that symbols are drawn independently from a fixed distribution $p$ .
The Huffman bound in Section 4 ( $H(X) \le L_{\text{Huffman}} < H(X)+1$ ) is a special case of this theorem, restricted to prefix-free symbol-by-symbol codes.

Proof of the bound, and decomposition of the gap. Alongside the cross entropy $H(p, q) = -\sum_x p(x)\log_2 q(x)$ of Section 2, define the relative entropy (Kullback-Leibler divergence)

$D(p | q) = \sum_x p(x) \log_2 \frac{p(x)}{q(x)}$

The proof of Theorem 2.1 is exactly the statement $D(p | q) \ge 0$ (Gibbs' inequality), with equality only if $q = p$ . Splitting the cross entropy,

$H(p, q) = H(p) + D(p | q)$

so Corollary 2.2's mismatch penalty is $D(p | q)$ bits per symbol.

Now take any uniquely decodable code with lengths $L$ . By Kraft-McMillan (Section 8), $Z = \sum_x 2^{-L(x)} \le 1$ , so $q_L(x) = 2^{-L(x)} / Z$ is a genuine distribution: the coding distribution the code implicitly assumes, in the sense of Corollary 2.2. Since $L(x) = -\log_2 q_L(x) - \log_2 Z$ ,

$E_p[L(X)] = H(p) + D(p | q_L) + \left(-\log_2 Z\right) \ge H(p)$

Both added terms are non-negative, and they name the two distinct ways a code wastes bits: $D(p | q_L)$ is the penalty for coding with the wrong distribution, and $-\log_2 Z$ is unused leaf space (Section 3's slack case). Equality requires $q_L = p$ and $Z = 1$ , that is, lengths exactly $-\log_2 p(x)$ , which is realizable with integer lengths only when every $p(x)$ is a power of $1/2$ . This extends Theorem 2.1 from relaxed symbol codes to every uniquely decodable code, and it identifies $D(p | q)$ as the per-symbol price of a model mismatch, which is what the adaptive and context models of Section 9 exist to reduce.

Almost sure version. For $X_1, \ldots, X_n$ i.i.d. from $p$ , independence turns the probability of the sequence into a product, so its information content is a sum,

$-\log_2 p(X_1, \ldots, X_n) = \sum_{i=1}^{n} h_p(X_i)$

of i.i.d. terms with mean $H(X)$ . By the strong law of large numbers,

$\frac{1}{n} \sum_{i=1}^{n} h_p(X_i) \to H(X) \quad \text{almost surely}$ $

So arithmetic coding (Section 5) spends $n H(X) + o(n)$ bits on almost every sequence, beyond the bound on the expectation. Equivalently, almost all the probability sits on about $2^{n H(X)}$ sequences of probability about $2^{-n H(X)}$ each, which $n H(X)$ bits can number (asymptotic equipartition property). For stationary ergodic sources (Section 10) the same holds with the entropy rate in place of $H(X)$ (Shannon-McMillan-Breiman theorem).

Entropy also measures uniformity: it is maximized (at $\log_2 N$ for $N$ symbols) when the distribution is uniform, and decreases as the distribution becomes more skewed. A skewed distribution is more predictable, hence more compressible, hence lower entropy.

8. Does dropping the prefix property help? (Kraft-McMillan)

Section 3 stated the Kraft inequality for prefix-free codes:

$\sum_x 2^{-L(x)} \le 1$

A broader class of codes exists: uniquely decodable codes. A code is uniquely decodable if every valid bitstream corresponds to exactly one sequence of symbols, without requiring that decoding proceed strictly left to right without lookahead. Prefix-free codes are uniquely decodable, but not every uniquely decodable code is prefix-free (some require reading ahead before resolving a symbol).

The McMillan theorem extends the Kraft inequality to this larger class: any uniquely decodable code, prefix-free or not, must satisfy the same inequality:

$\sum_x 2^{-L(x)} \le 1$

Combined with Section 3's result (any length assignment satisfying the Kraft inequality can be realized by a prefix-free code), this means: for any set of codeword lengths achievable by a uniquely decodable code, a prefix-free code with the same lengths also exists.

In other words: prefix-free codes lose nothing relative to the larger class of uniquely decodable codes.

Example with the non-prefix-free code from Section 3, A=0, B=01. It is uniquely decodable: every 1 in a valid stream must end a B, so a 0 followed by 1 is B, and a 0 followed by 0 (or by the end of the stream) is A. Decoding is unambiguous but needs one bit of lookahead. Its Kraft sum is $1/2 + 1/4 = 3/4 \le 1$ , as McMillan requires, so a prefix-free code with the same lengths exists: move B from below A to the free leaf 10.

9. What if we do not know the distribution?

Sections 1 to 8 assume the distribution $p(x)$ is fixed and known to both encoder and decoder in advance. Two ways this assumption fails in practice:

The distribution is not known in advance. Example: compressing an arbitrary text file without a precomputed frequency table.

The distribution changes across the message. Example: in English text, the probability of the next character depends heavily on the preceding characters ("q" is almost always followed by "u").

Adaptive Huffman coding addresses the first problem: the encoder and decoder both start with a default (for example, uniform) distribution, then update symbol counts and rebuild the Huffman tree as symbols are processed, using the same update rule on both ends so the tree stays synchronized without transmitting it separately.

Example: both sides start from a count of 1 for each of A, B, C, D, which gives a balanced tree. After A A A A B has been coded, both sides hold counts A=5, B=2, C=1, D=1, and the rebuilt tree gives A a 1-bit codeword. The decoder can make the identical update because it only uses symbols it has already decoded. (Practical versions, the FGK and Vitter algorithms, adjust the tree incrementally after each symbol instead of rebuilding it.)

Start, counts A=1, B=1, C=1, D=1:

flowchart TD
    a0((" ")) -->|0| a1((" "))
    a0 -->|1| a2((" "))
    a1 -->|0| aA["A = 00"]
    a1 -->|1| aB["B = 01"]
    a2 -->|0| aC["C = 10"]
    a2 -->|1| aD["D = 11"]

After A A A A B, counts A=5, B=2, C=1, D=1:

flowchart TD
    b0((" ")) -->|0| bA["A = 0"]
    b0 -->|1| b1((" "))
    b1 -->|0| bB["B = 10"]
    b1 -->|1| b2((" "))
    b2 -->|0| bC["C = 110"]
    b2 -->|1| bD["D = 111"]

Context models address the second problem: rather than a single distribution $p(x)$ , use a conditional distribution $p(x \mid \text{context})$ , where the context is the preceding $k$ symbols (an order- $k$ model). Order-0 corresponds to the fixed-distribution assumption used in sections 1 to 6. Higher orders capture local structure such as common letter pairs or triples.

Cost: the context model itself must be known to (or learned identically by) both encoder and decoder, and either transmitted or built adaptively. Larger $k$ captures more structure but requires more data to estimate the conditional probabilities reliably, and more memory to store them.

Arithmetic coding (Section 5) composes naturally with context models: at each step, the interval is subdivided using the distribution conditioned on the context so far, rather than a fixed distribution. This combination (context modeling plus arithmetic coding) is the basis of the compressors that get closest to the entropy of the true, context-dependent source. Section 10 compares them with the dictionary methods behind zip and 7-zip. Sections 14 to 16 work through Markov models, their entropy rates, and the cost of learning their probabilities.

10. Compressing repetition rather than frequency (LZ77, LZ78, LZW)

Sections 1 to 9 all encode based on symbol probability, whether fixed (Huffman, Section 4) or context-dependent (Section 9). Dictionary methods use a different mechanism: exploiting repeated substrings rather than symbol frequency.

LZ77: maintains a sliding window over recently seen data. When the upcoming text matches a substring already present in the window, output a reference (offset, length) pointing back to that earlier occurrence, instead of the literal symbols. Example: encoding "...information theory... more information theory here" can replace the second "information theory" with a pointer to the first, plus a length.

LZ78: builds an explicit dictionary of substrings seen so far, incrementally, and outputs indices into that dictionary rather than window offsets. LZW is a common variant that initializes the dictionary with all single symbols and grows it as the input is processed, without needing to transmit the dictionary explicitly (the decoder reconstructs it using the same rule).

Example, LZ78 on ABAABABAABAB. At each step, find the longest dictionary entry matching the upcoming input, output (its index, the next symbol), and add the extended phrase as a new entry. Index 0 is the empty phrase.

Step	Longest match (index)	Next symbol	Token	New entry
1	empty (0)	A	(0, A)	1: A
2	empty (0)	B	(0, B)	2: B
3	A (1)	A	(1, A)	3: AA
4	B (2)	A	(2, A)	4: BA
5	BA (4)	A	(4, A)	5: BAA
6	BA (4)	B	(4, B)	6: BAB

The input parses as A | B | AA | BA | BAA | BAB. The dictionary is a trie: each entry is an existing entry plus one symbol, which is exactly what a token records, so each token adds one child node.

flowchart TD
    R["0: empty"] -->|A| N1["1: A"]
    R -->|B| N2["2: B"]
    N1 -->|A| N3["3: AA"]
    N2 -->|A| N4["4: BA"]
    N4 -->|A| N5["5: BAA"]
    N4 -->|B| N6["6: BAB"]

Finding the longest match is a walk down this trie following the input, stopping when the next symbol has no edge. Two contrasts with the code trees of Sections 3 and 4: symbols label edges rather than leaves, and every node (internal ones included) is a usable entry, since each phrase is by construction a prefix of later phrases. On an input this short, 6 tokens cost more bits than the 12 raw symbols; the gain appears on long inputs, where the trie deepens and later tokens cover longer and longer phrases.

Where this fits in the framework of sections 1 to 9: LZ methods do not directly assign $-\log_2 p(x)$ style lengths to individual symbols. Instead, they transform the input into a shorter sequence of (symbol, pointer) tokens, exploiting redundancy across positions (repeated phrases) rather than redundancy within the marginal symbol distribution. The token stream that results is often then entropy-coded (Huffman or arithmetic coding) as a second stage. gzip and DEFLATE combine LZ77 with Huffman coding in exactly this two-stage structure.

Relation to entropy: LZ77 and LZ78 can be shown to asymptotically approach the entropy rate of a stationary ergodic source (a source whose statistics do not change over time and whose long-run behavior is representative of any given sample) as the window or dictionary size grows, without requiring the encoder to know the source distribution in advance. This is a different route to the same entropy limit described in Section 7, arrived at without explicit probability estimation. The entropy rate is $\lim_{n} \frac{1}{n} H(X_1, \ldots, X_n)$ , the entropy of Section 7 applied to blocks of $n$ symbols, per symbol. It equals $H(X)$ for an i.i.d. source and is smaller when symbols are dependent, the structure Section 9's context models exploit.

Why dictionary methods are used. No model is estimated or transmitted: the decoder rebuilds the dictionary from the message, so the method is universal. Decoding LZ77 is a sequence of byte copies, far cheaper than a context model plus arithmetic coder at every symbol. And a repeated phrase of hundreds of bytes is one token, where an order- $k$ model re-predicts it symbol by symbol.

Are they less optimal? Asymptotic optimality does not settle performance on finite files. Redundancy bounds depend on the source class and the precise algorithm; there is no uniform convergence rate over all stationary ergodic sources. For a fixed finite-alphabet Markov order, adaptive context coding can have $O(\log n / n)$ overhead per symbol relative to the best model of that order (Section 16). Entropy coding the tokens (offsets, lengths, literals) as a second stage recovers part of the gap, since they are far from uniform. The best text compressors drop LZ and mix many context models into an arithmetic coder, at 100 to 1000 times the compute. Sizes on enwik8 (first 100 MB of English Wikipedia, Large Text Compression Benchmark):

Compressor	Mechanism	Output	bits/byte
gzip	LZ77 (32 KB window) + Huffman	36.4 MB	2.92
bzip2	Burrows-Wheeler transform + Huffman	29.0 MB	2.32
zstd	LZ77 (large window) + Huffman and tANS	25.4 MB	2.03
xz (LZMA, as in 7-zip)	LZ77 (large window) + range coder with adaptive bit models	24.7 MB	1.98
7-zip PPMd	order- $k$ context model + range coder, no LZ	21.2 MB	1.70
cmix	context mixing + arithmetic coder, no LZ	14.6 MB	1.17

The familiar tools. zip and gzip: DEFLATE, LZ77 with a 32 KB window plus Huffman. 7-zip: LZMA, LZ77 with a window up to gigabytes, tokens coded bit by bit by a range coder (Section 11) under small adaptive context models (Section 9). Its PPMd mode is a pure context model, better on text. RAR: LZ77 with a window up to 1 GB plus Huffman (RAR3 also had a PPMd mode, dropped in RAR5). bzip2: the Burrows-Wheeler transform sorts the rotations of the block, which puts symbols with the same context next to each other, so an order-0 coder captures context structure.

BPE. Byte-pair encoding began as a compressor (Gage, 1994): replace the most frequent adjacent pair by a new symbol, record the replacement, repeat. The vocabulary is a dictionary in the LZ78 sense, built by extending existing entries. Unlike LZ, it is fitted once and fixed, so it costs storage (LZ rebuilds its dictionary for free) but applies to new text without restarting from empty, and it emits no pointers: the vocabulary is the alphabet of the second stage. In a language model that stage is a context model over tokens with arithmetic coding, so the model's bits per byte is the code length of a gzip-shaped two-stage compressor. Tokens per byte measures only the first stage's output length, like judging gzip by its LZ77 token count before Huffman coding.

11. Arithmetic coding in finite precision (range coding)

Section 5 described arithmetic coding using real-number intervals within $[0,1)$ . Real hardware and software use fixed-precision arithmetic (32-bit or 64-bit integers), not arbitrary-precision real numbers.

Range coding is the practical implementation strategy: it performs the same interval-narrowing operation as Section 5, but represents the current interval using a fixed number of bits, renormalizing (shifting out bits that are already determined and rescaling) as the interval shrinks below the precision limit, instead of tracking an ever more precise real number.

Two practical differences from the idealized version in Section 5:

Precision is bounded. Care is required in the renormalization step to avoid a carry (a small addition affecting more digits than the currently tracked range) propagating beyond the tracked precision.
The underlying base is often not restricted to binary subdivision; some range coders subdivide using byte-aligned ranges (base 256) for speed, rather than bit-by-bit as in Section 5's binary framing.

Range coding is used in place of "textbook" arithmetic coding in most production compressors (for example, in modern image and video codecs, and in general-purpose compressors such as those using PAQ-family or CM-family entropy stages), because it achieves the same near-entropy performance described in Section 5 without requiring arbitrary-precision arithmetic.

12. Sending bits over a noisy channel (channel coding)

Sections 1 to 11 address source coding: representing data compactly, assuming the encoded bits are transmitted or stored without alteration. Channel coding addresses the complementary problem: transmitting bits reliably over a channel that introduces errors.

The channel. One input bit per use, one output bit. The binary symmetric channel with parameter $\epsilon$ flips each bit independently with probability $\epsilon$ (symmetric: $0 \to 1$ and $1 \to 0$ are equally likely). It is the channel counterpart of the i.i.d. source of Section 1.

Rate. To protect $k$ message bits the sender transmits $m \ge k$ channel bits, and the rate $R = k/m$ is the fraction that carries the message. A code is a set of $2^{mR}$ codewords in ${0,1}^m$ , and the decoder maps each received word to the most likely codeword. Example: repeat each bit three times, decode by majority. $R = 1/3$ , and a bit is wrong when two or three copies flip, probability $3\epsilon^2(1-\epsilon) + \epsilon^3 \approx 0.028$ at $\epsilon = 0.1$ . More repetition lowers the error and the rate together.

Capacity. $C$ is the largest rate at which the error can be driven to zero at fixed rate: for every $R < C$ and $\delta > 0$ there is a block length $m$ and a code of rate $R$ with error probability below $\delta$ . The block length grows as $\delta$ shrinks, and the existence proof does not construct the code. It is the "code the whole sequence at once" move of Section 5, now used to average out noise. For the binary symmetric channel,

$C = 1 - H_2(\epsilon), \quad H_2(\epsilon) = -\epsilon \log_2 \epsilon - (1-\epsilon)\log_2(1-\epsilon)$

$H_2(\epsilon)$ is the entropy of Section 7 for the distribution $(\epsilon, 1 - \epsilon)$ : of the one bit each received bit carries, $H_2(\epsilon)$ bits are uncertainty about whether it was flipped, and the code has to spend that much redundancy to resolve it. So $C$ is the largest fraction of usable message bits per transmitted bit, and $1 - C$ the smallest error-correction overhead. At $\epsilon = 0.1$ , $H_2 \approx 0.469$ (the skewed source of Section 5) and $C \approx 0.531$ : at most 53 message bits per 100 transmitted. At $\epsilon = 0.5$ the output is independent of the input and $C = 0$ . For larger input alphabets $C$ is in bits per channel use and can exceed 1.

Noisy-channel coding theorem (Shannon). For any rate $R < C$ there exist codes with arbitrarily low error probability. For $R > C$ there are none.

Error-correcting codes are the practical realizations of this theorem: adding structured redundancy to a message so the receiver can detect and correct a bounded number of errors. Examples include Hamming codes, Reed-Solomon codes, and LDPC codes.

Relation to source coding, sections 1 to 11: source coding minimizes redundancy (compress toward $H(X)$ , Section 7), channel coding adds redundancy back in a structured way to survive noise. Shannon's separation theorem states that, for point-to-point communication, source coding and channel coding can be designed separately (compress optimally, then add error correction optimally) without loss of overall efficiency compared to a jointly designed scheme. This justifies treating them as two separate topics, as done here.

13. What if some error is acceptable? (rate-distortion)

Sections 1 to 12 assume lossless reconstruction: the decoder recovers the exact original sequence. Rate-distortion theory addresses lossy coding: how few bits are needed if some reconstruction error is acceptable.

Distortion measure $d(x, \hat{x})$ : a chosen function quantifying the cost of reconstructing symbol $x$ as $\hat{x} \neq x$ (for example, squared error for continuous-valued sources).

Rate-distortion function $R(D)$ : the minimum bit rate (bits per symbol) required to achieve average distortion no greater than $D$ , over all encoding schemes:

$R(D) = \min_{p(\hat{x}\mid x): E[d(x,\hat{x})] \le D} I(X; \hat{X})$

where the minimum runs over conditional distributions of the reconstruction given the source, and the mutual information

$I(X; \hat{X}) = D\big(p(x, \hat{x}) | p(x) p(\hat{x})\big)$

is the relative entropy (Section 7) of the joint law from the product of its marginals. It is 0 when $\hat{X}$ is independent of $X$ and $H(X)$ when $\hat{X} = X$ , so $0 \le R(D) \le H(X)$ .

At $D=0$ (no distortion allowed), $R(D)$ reduces to $H(X)$ for a discrete source, recovering the lossless bound from Section 7. As the allowed distortion $D$ increases, $R(D)$ decreases: less precision is needed if some error is tolerated.

Practical lossy compressors (JPEG for images, MP3 and Opus for audio, most video codecs) operate by first applying a transform intended to concentrate distortion where it is least perceptible (for example, a frequency-domain transform paired with a model of human perceptual sensitivity), then discarding or coarsely quantizing the least perceptually important components, then applying lossless entropy coding (Huffman or arithmetic coding, Sections 4 to 5, often with context modeling, Section 9) to the remaining quantized data. The rate-distortion function gives the theoretical bound these systems are measured against.

14. Conditional entropy: the coding value of context

Section 9 introduced context models without quantifying their savings. Consider a source that chooses its first bit by a fair coin, then alternates forever:

first bit 0: 010101010101...
first bit 1: 101010101010...

At every position, the marginal distribution is uniform: $p(X_t=0)=p(X_t=1)=1/2$ . A coder using only that distribution spends one bit per symbol. Yet, once the first bit is known, the entire sequence is determined. If the length $n$ and the alternation rule are shared, the whole message costs one bit.

Conditional entropy. For two discrete random variables,

$H(Y\mid X) = \sum_x p(x)H(Y\mid X=x) = -\sum_{x,y}p(x,y)\log_2 p(y\mid x)$

It averages the uncertainty remaining about $Y$ after $X$ is known. In the alternating source, $H(X_t)=1$ but $H(X_t\mid X_{t-1})=0$ . Knowing the previous bit removes all uncertainty about the next one. In an i.i.d. fair-coin source, both quantities are 1: the previous bit tells us nothing.

Probability chain rule. Write $x_1^n=(x_1,\ldots,x_n)$ . The probability chain rule, which requires no independence assumption, gives

$p(x_1^n)=p(x_1)\prod_{t=2}^{n}p(x_t\mid x_1^{t-1})$

Taking negative logarithms gives the ideal sequential code length. Its expectation gives the entropy chain rule:

$H(X_1^n)=H(X_1)+\sum_{t=2}^{n}H(X_t\mid X_1^{t-1})$

For independent symbols this is $nH(X_1)$ . For our alternating source it is $1+0+\cdots+0=1$ . The corresponding entropy rate is $\lim_{n\to\infty}H(X_1^n)/n=0$ . Nothing violates Section 7's entropy bound: the joint distribution is supported on only two length- $n$ messages, rather than all $2^n$ binary strings.

Context savings. In expectation, the saving from knowing $X$ when coding $Y$ is

$H(Y)-H(Y\mid X)=I(X;Y)$

the mutual information introduced in Section 13. Conditional entropy is the minimum expected ideal length when the context is shared. A particular context can still make an outcome more surprising. See the Stanford notes on the entropy chain rule for the general identities.

Assume the length $n$ is shared or charged separately, as in Section 5. Conditioning on the entire past motivates the finite-memory models below.

15. Markov codes: finite context

Remembering the entire past is expensive. An order- $k$ Markov model keeps only the last $k$ symbols when predicting at positions $t>k$ :

$q(x_t\mid x_1^{t-1})=q(x_t\mid x_{t-k}^{t-1})$

Order 0 ignores the past, order 1 remembers the previous symbol, and order 2 remembers the previous pair. The equality is an assumption about the model $q$ . A real source need not satisfy it.

A Markov code is a lossless source code driven by these conditional probabilities. The model supplies predictions, and Huffman or arithmetic coding turns them into bits.

Transition table. Replace the deterministic rule in Section 14 by a 90% chance of switching bits:

Previous bit	Next is 0	Next is 1
0	0.1	0.9
1	0.9	0.1

Start with a fair first bit. The marginal distribution then remains uniform at every position. This is the stationary distribution $\pi=(1/2,1/2)$ : if the current state has distribution $\pi$ , applying the transition table produces the same distribution again.

flowchart LR
    Z(("0")) -->|"next 1: 0.9"| O(("1"))
    O -->|"next 0: 0.9"| Z
    Z -->|"next 0: 0.1"| Z
    O -->|"next 1: 0.1"| O

Each state is the previous symbol. Edges give the next symbol and its probability.

Arithmetic coding example. Given the table above, a fair initial bit, and the message 0101,

$q(0101)=\tfrac12\times 0.9\times 0.9\times 0.9=0.3645$

Its ideal length is $-\log_2 0.3645\approx1.456$ bits, compared with 4 bits under the uniform order-0 model. Arithmetic coding uses a different row of the table after each symbol. Keeping the symbol order 0 then 1 within every interval:

Prefix decoded	Distribution used for this step	Current interval
empty	initial state	$[0,1)$
`0`	initial $(0.5,0.5)$	$[0,0.5)$
`01`	after 0: $(0.1,0.9)$	$[0.05,0.5)$
`010`	after 1: $(0.9,0.1)$	$[0.05,0.455)$
`0101`	after 0: $(0.1,0.9)$	$[0.0905,0.455)$

The final width is $0.3645$ , exactly the sequence probability. The 3-bit string 001 names $[0.125,0.25)$ , which fits inside the final interval. No 2-bit interval fits. With the model and length shared, this particular message therefore costs 3 bits under Section 5's construction. The decoder recovers each symbol before needing it to select the next row, so no separate sequence of states is transmitted.

Entropy rate. A switch costs $-\log_2 0.9\approx0.152$ ideal bits, and a repeated bit costs $-\log_2 0.1\approx3.322$ . Their average is

$\bar H=0.9(-\log_2 0.9)+0.1(-\log_2 0.1)=H_2(0.1)\approx0.469\text{ bits/symbol}$

More generally, for a stationary first-order Markov source with transition probabilities $p(b\mid a)$ ,

$\bar H=H(X_2\mid X_1)=\sum_a\pi(a)H\big(p(\cdot\mid a)\big)$

and $H(X_1^n)=H(\pi)+(n-1)\bar H$ . The Stanford notes on Markov entropy rates derive this relation. In our example, a 1,000-symbol message has expected ideal length about $1+999H_2(0.1)\approx469.53$ bits, before the arithmetic coder's final rounding, instead of 1,000 bits under the marginal model.

A Markov code exploits conditional probabilities even when the marginal distribution is uniform. A separate binary Huffman tree in each state would still cost one bit per transition: both possible next symbols need a nonempty codeword. Arithmetic coding, or Huffman coding of longer blocks, is needed to realize the fractional rate.

Order-2 example. Choose a random starting phase of the repeating sequence 001100110011.... Each bit is marginally fair. After either bit, 0 and 1 follow with equal probability. An order-1 model gains nothing. But pairs determine the next bit:

Last two bits	Next bit
`00`	1
`01`	1
`11`	0
`10`	0

An order-2 model sends the first two bits and then predicts everything exactly. The entropy rate is again zero. For an alphabet of size $m$ , however, a full order- $k$ table has $m^k$ rows and $m^k(m-1)$ free probabilities. Increasing memory quickly makes learning the table a statistical problem.

16. Adaptive Markov codes: learning the probabilities

So far, the transition table was shared in advance. If it is unknown, the encoder could estimate it from the whole message and transmit it first. Alternatively, encoder and decoder can learn the same table from the prefix already processed, as in adaptive Huffman coding in Section 9.

For each context $s$ , keep counts $N_t(s,a)$ of how often symbol $a$ has followed $s$ strictly before position $t$ . Let $N_t(s)=\sum_aN_t(s,a)$ . A naive frequency estimate $N_t(s,a)/N_t(s)$ is undefined in an unseen context and assigns zero probability to an unseen continuation. Zero probability would require infinitely many bits.

A simple fix is the Krichevsky–Trofimov (KT) predictor, which starts every count at one half:

$q_t(a\mid s)=\frac{N_t(s,a)+1/2}{N_t(s)+m/2}$

For a binary alphabet the denominator is $N_t(s)+1$ . Both sides use this distribution to code or decode the next symbol, then increment its count. The counts must use only symbols already decoded.

Example: learn an order-1 model on 0101. Use a fair distribution for the first bit and separate count tables for contexts 0 and 1:

Position	Symbol	Context	Counts $(N_t(s,0),N_t(s,1))$ before coding	Probability assigned
1	0	start	no counts	$1/2$
2	1	0	$(0,0)$	$1/2$
3	0	1	$(0,0)$	$1/2$
4	1	0	$(0,1)$	$3/4$

The joint probability is $3/32$ , so the ideal length is $\log_2(32/3)\approx3.415$ bits. Learning costs more on this short message than knowing the 90% switching model in Section 15. On the fourth symbol, the predictor has only one previous observation of what follows 0. Had the next symbol instead been 0, it would still receive probability $1/4$ , so the decoder could handle it.

Learning cost. For binary i.i.d. data, the KT sequence code is within $\tfrac12\log_2 n+O(1)$ bits of the best fixed Bernoulli parameter chosen after seeing the data. This is a regret bound: a comparison with an oracle that gets to fit its parameter for free. Applying a KT predictor separately in each context gives an $O(2^k\log n)$ bound for fixed-order binary Markov models, with initial symbols handled separately. See the Stanford notes on KT estimation and tree sources.

For fixed $k$ , this overhead divided by $n$ tends to zero. If the source really is a stationary ergodic Markov source of that order, the adaptive code approaches its entropy rate without knowing its transitions in advance. This is universality relative to a source class. It does not say that a small sample suffices, or that a fixed-order predictor discovers every possible regularity.

In particular, if we increase $k$ so much that almost every context is new, the KT predictor keeps returning nearly uniform probabilities. In the binary case it then spends close to one bit per symbol, even if an in-sample table could memorize every observed transition. An adaptive code pays for learning through its prediction probabilities.

17. Two-part descriptions: paying for the model

There is another way to account for learning: describe a model explicitly, then describe the data using it. For a finitely specified model $M$ with distribution $q_M$ ,

$L_{\mathrm{total}}(x_1^n,M)=L(M)+L(x_1^n\mid M)\approx L(M)-\log_2 q_M(x_1^n)$

Here $L(M)$ includes whatever the receiver lacks: the model family, order, and parameters at the precision actually used by the coder. The decoding convention must be fixed in advance, and the model description must have a recognizable end. Any unshared message length is also charged.

Self-delimiting lengths. For a positive integer $n$ , write its binary representation, which has $b=\lfloor\log_2 n\rfloor+1$ bits, and precede it with $b-1$ zeros. This is an Elias gamma code:

$n$	Binary	Gamma code
1	`1`	`1`
2	`10`	`010`
3	`11`	`011`
4	`100`	`00100`
13	`1101`	`0001101`

To decode 0001101, count three leading zeros, then read four bits starting with the first 1: 1101, or 13. The code ends after $2\lfloor\log_2 n\rfloor+1$ bits. We can therefore send a length followed by exactly that many raw bits, with no ambiguity about the boundary. Zero can be accommodated by coding $n+1$ .

Model selection example. Suppose our format has a 1-bit mode flag and then the gamma-coded length. Mode 0 means "read $n$ literal bits." Mode 1 means "read one starting bit and alternate for $n$ positions." Both modes reconstruct exactly, but mode 1 is available only for alternating strings.

For 0101010101010101, $n=16$ has a 9-bit gamma code. Literal mode costs $1+9+16=26$ bits. Alternating mode costs $1+9+1=11$ bits. The rule is built into the shared format, and the flag pays for choosing it. On less regular data, the literal mode remains available.

This is a small, fully specified instance of selecting a description by total length. The two-part minimum description length (MDL) rule does the same with a chosen family of models:

$\widehat M\in\operatorname*{argmin}_M\big\lbrace L(M)+L(x_1^n\mid M)\big\rbrace$

A richer Markov table must save enough bits in the data to pay for its description. Selecting the model from the data is allowed because the receiver is told which model won. The coding scheme for models must already be agreed upon. Grünwald's MDL tutorial develops this principle and its alternatives, including sequential codes such as those in Section 16.

Memorization. One can always propose a model that assigns probability 1 to the observed message. Its data term is zero, but specifying that model requires identifying the message. For a string with no available shorter description, this merely moves its bits into $L(M)$ .

The two-part rule selects the model that minimizes model-plus-data length. Performance on new messages is a separate question, measured by their code lengths under the selected model. A table sent once can be reused, but poor predictions still cost bits on every future message.

18. Kolmogorov complexity: shortest programs

A Markov table describes local regularity. The alternation mode in Section 17 describes a rule. We can allow more rules: repeat a block, print a multiplication table, or generate the binary representations of successive integers and concatenate them.

For that last example, the blocks begin

1 | 10 | 11 | 100 | 101 | 110 | 111 | 1000 | ...

A program can reproduce the first $n$ bits by counting upward, writing each integer in binary, and stopping at length $n$ . Its description contains the rule and $n$ . A transition table only conditions on a suffix, so its ability to compress does not exhaust the descriptions available to a program.

This suggests letting the decoder be a general-purpose computer. The compressed message is then a program that prints the desired string and halts.

Definition. Fix an optimal universal prefix machine $U$ : an interpreter for binary programs whose halting inputs form a prefix-free set. The prefix Kolmogorov complexity of a finite binary string $x$ is

$K_U(x)=\min_{p:U(p)=x}|p|$

$U(p)=x$ means the program outputs exactly $x$ and halts. We normally fix $U$ and write $K(x)$ . Kolmogorov complexity measures the shortest program, irrespective of its running time or working memory. See Shen's introduction for the formal construction.

The prefix condition connects this definition to Sections 3 and 8: programs are self-delimiting descriptions. A related quantity, plain complexity $C(x)$ , allows arbitrary finite programs whose input boundary is supplied externally. The distinction changes length bounds, so we will use $K$ consistently here.

Program upper bounds. For an alternating string of even length $n$ , a fixed program can read a gamma-coded $n$ and print 01 exactly $n/2$ times. Thus

$K\big((01)^{n/2}\big)\le 2\lfloor\log_2 n\rfloor+O(1)$

The constant contains the loop and interpreter instructions. The same bound applies to the first $n$ bits of the integer-concatenation sequence above, using its own fixed generation routine. A million output bits can therefore have a description whose variable part is only a few dozen bits. This does not give an exact byte count for a Python script: the definition counts a binary program in a fixed machine.

For any string, an available fallback is "read a self-delimiting length, copy that many literal bits, and halt." It gives $K(x)\le |x|+O(\log |x|)$ . The sharper standard bound is

$K(x)\le |x|+K(|x|)+O(1)$

because we can use a shortest description of the integer length. Plain complexity has the simpler bound $C(x)\le |x|+O(1)$ because its input length is already delimited.

Conditional complexity. Conditional complexity $K(x\mid y)$ is the shortest program that prints $x$ when $y$ is supplied as auxiliary input, without charging for $y$ . An alternating string has $K(x\mid n)=O(1)$ when $n$ is given. Also $K(x\mid x)=O(1)$ : a fixed program copies its input. This is the same accounting choice made when sharing a probability table or a dictionary with a decoder.

Invariance theorem. For any two fixed optimal universal prefix machines $U$ and $V$ , there is a constant $c_{U,V}$ such that

$|K_U(x)-K_V(x)|\le c_{U,V}$

This holds for every $x$ : one interpreter can simulate the other with a fixed wrapper. The constant is independent of the string, but it can matter for short strings. The machine must be fixed before comparing messages: giving each string its own built-in "print this" instruction would hide the data in the decoder again.

19. Incompressibility and noncomputability

The examples above have short generating rules. How common are such strings?

Counting argument. There are $2^n$ binary strings of length $n$ , but only

$1+2+\cdots+2^{n-c-1}=2^{n-c}-1$

binary programs shorter than $n-c$ bits, for integers $0\le c<n$ . Each halting program outputs at most one string. Therefore

$\left|\lbrace x\in\lbrace 0,1\rbrace^n:K(x)<n-c\rbrace\right|<2^{n-c}$

Fewer than a fraction $2^{-c}$ of length- $n$ strings have descriptions that short. With $c=10$ , fewer than one in 1,024 strings can be described in fewer than $n-10$ bits. This fraction is under the uniform distribution on length- $n$ strings.

A finite string with $K(x)$ close to its length is called incompressible, or algorithmically random up to the chosen deficiency. Passing a frequency test is much weaker. The alternating string has perfectly balanced zeros and ones but a tiny generating program. A string may pass many local tests and still have a short global description.

Noncomputability. We can run all candidate programs in parallel, giving each progressively more computation. Whenever one halts with output $x$ , it supplies an upper bound on $K(x)$ . The difficulty is knowing that no shorter program will eventually produce $x$ . Some candidates never halt.

No algorithm can always halt and return the exact $K(x)$ for every finite string $x$ . A diagonal argument explains why. Suppose such an algorithm existed. Given an integer $m$ , enumerate strings in order of length, breaking ties lexicographically, and return the first string whose computed complexity is at least $m$ . Counting guarantees that the search eventually finds one. But the search itself is a fixed program plus a description of $m$ , requiring only $O(\log m)$ bits. For large enough $m$ , this describes the selected string in fewer than $m$ bits, contradicting how it was selected. The formal noncomputability argument makes this obstruction precise.

Consequently, a working compressor supplies an upper bound rather than a general certificate of optimality. If a lossless compressor produces a self-delimiting archive of length $\ell$ for $x$ , a fixed program can run its decompressor, giving

$K(x)\le\ell+c_{\mathrm{decoder}}$

If the archive needs external framing or a dictionary, those must be described too. Failure by gzip, a Markov coder, or a language model to compress a string does not prove that the string has high Kolmogorov complexity. A short program may also take impractically long to run, so the theoretical optimum need not be a useful compressor.

20. Shannon entropy and expected Kolmogorov complexity

Shannon entropy describes the expected coding cost under a distribution. Kolmogorov complexity describes one particular object, relative to a fixed universal interpreter. They are connected by the same model-plus-data construction used in Section 17.

Let $q$ be a computable probability mass function on finite binary strings: a finite program can approximate its probabilities to any requested precision. Write $K(q)$ for the length of a shortest such description. For $q(x)>0$ ,

$K(x)\le K(q)+\left\lceil-\log_2 q(x)\right\rceil+O(1)$

A description of $q$ , followed by a probability code for $x$ , is one possible program for reconstructing $x$ . The shortest program can only be shorter. If $q$ is a distribution over strings of a fixed length $n$ , specifying that $n$ is part of describing $q$ , unless it is supplied as auxiliary information.

Averaging gives, for a computable distribution with finite entropy,

$H(q)\le\mathbb{E}_{X\sim q}[K(X)]\le H(q)+K(q)+O(1)$

The lower bound follows from Kraft because shortest prefix programs form a prefix code. The upper bound comes from the preceding construction. These are the bounds in Grünwald and Vitányi's comparison of Shannon information and Kolmogorov complexity, Section 2.3.

Model dependence. Under a fair i.i.d. model, a particular length- $n$ alternating string has probability $2^{-n}$ , hence surprisal $n$ bits. Its Kolmogorov complexity is only $O(\log n)$ because a loop generates it. Under the shared alternating-source model of Section 14, the same string has probability $1/2$ and needs only one data bit, plus the length if it is not shared. The difference comes from the model and the information available to the decoder.

There is no requirement that an individual string's shortest description equal its surprisal under every model. Shannon's lower bound concerns the average over the specified source. Saving many bits on its rare alternating outputs cannot lower the average below the source entropy.

Expected prefix complexity lies between the source entropy and that entropy plus the description cost of the source, up to a fixed constant.