Universal Source Coding

Motivation: the telecom doesn’t know who is typing

Every compression result so far assumed the engineer knows the source distribution $p$ . Huffman needs $p$ to merge the two least likely symbols. Shannon–Fano–Elias needs $p$ to build the CDF. The wrong-code theorem showed that guessing $q$ instead of $p$ costs $D(p \Vert q)$ bits per symbol.

On a real telegraph line the company serves thousands of operators, in different languages, on different topics, and it cannot interview each one before the message arrives. There are three escalating versions of this ignorance:

What the engineer knows	Approach	Section
The source is one of a known family $\{p_\theta\}$ , $\theta$ unknown	A single code that is good for every member: minimax redundancy	Universal codes and channel capacity
Nothing, but the data can be read once, in order	Learn the distribution on the fly and feed the estimate to an arithmetic coder	Universal coding for binary sequences, Arithmetic coding
No distribution at all, just an individual sequence (a book, a song)	Adaptive dictionaries: Lempel–Ziv	Lempel–Ziv coding

IntuitionWhy “two passes” isn’t the answer

One fix is to read the whole message, estimate $p$ , build a Huffman code, then go back and encode, sending the code table too. This works for small files but fails for a live line: the operator is still typing when the first pulses must leave. We want one-pass (online) coders that learn as they go, and still converge to the entropy.

WarningIndividual-sequence compression needs a benchmark

“Compress this particular sequence as well as possible” is meaningless without restricting the class of compressors. For any sequence there is a function that maps that sequence to one bit and leaves every other one alone. It is perfectly overfitted. So for individual sequences we compare against benchmarks such as the best Bernoulli or $k$ -th-order Markov code chosen in hindsight. The ultimate benchmark, Kolmogorov complexity, comes in Chapter 14.

Universal codes and channel capacity

Setup. $X$ is drawn from one of $m$ distributions $p_\theta$ , $\theta \in \{1, \ldots, m\}$ , and we don’t know which. Throughout this section we ignore the integer constraint on codeword lengths, which costs at most one bit (Shannon codes).

If $\theta$ were known, lengths $l(x) = \log \frac{1}{p_\theta(x)}$ would give the best possible expected length:

$\min_{l} \mathbb{E}_{p_\theta}[l(X)] = H(p_\theta)$

DefinitionRedundancy

A code with lengths $l(x)$ implicitly assumes the distribution $q(x) = 2^{-l(x)}$ . Its redundancy against source $p_\theta$ is the excess over the ideal:

$R(p_\theta, q) = \mathbb{E}_{p_\theta}[l(X)] - H(p_\theta) = \sum_x p_\theta(x)\left(\log\frac{1}{q(x)} - \log\frac{1}{p_\theta(x)}\right) = D(p_\theta \,\Vert\, q)$

Component	Detail
Signature	$R : \mathcal{P}(\mathcal{X}) \times \mathcal{P}(\mathcal{X}) \rightarrow [0, \infty]$
Domain	The true source $p_\theta$ and the coding distribution $q$ the codebook was built for.
Codomain	Extra bits per symbol paid for not knowing $\theta$ .

DefinitionMinimax redundancy

The worst-case redundancy of the best single code:

$R^* = \min_q \max_\theta R(p_\theta, q) = \min_q \max_\theta D(p_\theta \,\Vert\, q)$

IntuitionThe center of an information ball

Picture the distributions $p_1, \ldots, p_m$ as points. $R^*$ asks for the point $q^*$ whose farthest source is as close as possible, measured in relative entropy. It is the center of the smallest “relative entropy ball” enclosing every candidate source, and $R^*$ is that ball’s radius (the information radius of the family).

flowchart LR
  P1["p_1"] --- Q["q*: center of the ball"]
  P2["p_2"] --- Q
  PM["p_m"] --- Q

The channel from parameter to source

To find $q^*$ , view the unknown parameter as the input of a channel and the source symbol as its output. Row $\theta$ of the transition matrix is $p_\theta$ :

flowchart LR
  T["theta: which source"] -->|"row theta of the matrix is p_theta"| X["X: source symbol"]

An input distribution $\pi(\theta)$ induces the output distribution $q_\pi(x) = \sum_\theta \pi(\theta) p_\theta(x)$ , and the channel’s capacity is

$C = \max_\pi I(\theta; X) = \max_\pi \sum_\theta \pi(\theta) \sum_x p_\theta(x) \log \frac{p_\theta(x)}{q_\pi(x)}$

NoteChannel capacity

Capacity is the subject of Chapter 7 (see channel-capacity). For this note only the definition $C = \max_\pi I(\theta;X)$ is needed.

TheoremMinimax redundancy is capacity (Gallager; Ryabko)

The capacity of the channel with rows $p_1, \ldots, p_m$ is

$C = R^* = \min_q \max_\theta D(p_\theta \,\Vert\, q)$

The minimizing $q$ is the output distribution induced by the capacity-achieving input distribution $\pi^*$ : $q^*(x) = \sum_\theta \pi^*(\theta) p_\theta(x)$ .

ProofA centroid identity, then the minimax theorem

Write $p_{ij} = p_\theta(x)$ for $\theta = i$ , $x = j$ , and $(q_\pi)_j = \sum_i \pi_i p_{ij}$ .

Step 1: Mutual information is an average distance to the centroid.

$I_\pi(\theta; X) = \sum_{i,j} \pi_i p_{ij} \log \frac{p_{ij}}{(q_\pi)_j} = \sum_i \pi_i D(p_i \,\Vert\, q_\pi)$

Step 2: Replace the centroid by any $q$ . Insert $q_j/q_j$ in the log and split:

$I_\pi = \sum_{i,j} \pi_i p_{ij}\log\frac{p_{ij}}{q_j} + \sum_{i,j}\pi_i p_{ij}\log\frac{q_j}{(q_\pi)_j}$

In the second sum, $\sum_i \pi_i p_{ij} = (q_\pi)_j$ , so it equals $-D(q_\pi \Vert q)$ . Hence

$\sum_i \pi_i D(p_i \,\Vert\, q) = I_\pi(\theta;X) + D(q_\pi \,\Vert\, q)$

Step 3: The centroid is the closest point on average. Since $D(q_\pi \Vert q) \ge 0$ , with equality iff $q = q_\pi$ ,

$I_\pi(\theta;X) = \min_q \sum_i \pi_i D(p_i \,\Vert\, q)$

So $C = \max_\pi \min_q \sum_i \pi_i D(p_i \Vert q)$ .

Step 4: Swap max and min. The objective is convex in $q$ (convexity of relative entropy) and linear, hence concave, in $\pi$ . Both range over compact convex sets (probability simplices). The minimax theorem of game theory says that for such $f$ , $\min_x \max_y f = \max_y \min_x f$ . So

$C = \min_q \max_\pi \sum_i \pi_i D(p_i \,\Vert\, q)$

Step 5: The inner maximum puts all weight on the worst source. A linear function of $\pi$ over the simplex is maximized at a vertex, so $\max_\pi \sum_i \pi_i D(p_i \Vert q) = \max_i D(p_i \Vert q)$ . Hence $C = R^*$ , and the saddle point gives $q^* = q_{\pi^*}$ .

∎

IntuitionThe parallel-axis theorem of information

Step 2 is the information-theoretic version of the parallel-axis theorem in mechanics: the average squared distance to any point equals the average distance to the centroid plus the distance from the centroid to that point. Here “squared distance” is relative entropy and the centroid is the mixture $q_\pi$ .

ImportantThe price of not knowing is a capacity

The cost of universality is the number of bits per symbol the source symbol $X$ reveals about which source produced it. If the candidate sources are very different, $X$ identifies $\theta$ easily, the channel has high capacity, and a single code must pay a lot. If they are similar, the channel is noisy and universality is cheap.

ExampleTwo sources that look like an erasure channel

$\mathcal{X} = \{1, 2, 3\}$ and

$p_1 = (1-\alpha,\ \alpha,\ 0), \qquad p_2 = (0,\ \alpha,\ 1-\alpha)$

The best universal coding distribution is the midpoint $q = \left(\frac{1-\alpha}{2},\ \alpha,\ \frac{1-\alpha}{2}\right)$ , with

$D(p_1 \Vert q) = D(p_2 \Vert q) = (1-\alpha)\log\frac{1-\alpha}{(1-\alpha)/2} + \alpha\log\frac{\alpha}{\alpha} = 1 - \alpha$

Seen as a channel, symbol 2 is an “erasure” (it says nothing about $\theta$ ), and symbols 1 and 3 reveal $\theta$ exactly. This is the binary erasure channel, with capacity $1 - \alpha$ at uniform input, whose output distribution is exactly $q$ . Not knowing the source costs $1 - \alpha$ bits per symbol above the entropy.

RemarkRedundancy is the gambler’s lost doubling rate

In the horse-race picture, a gambler betting $q$ when the truth is $p_\theta$ loses $D(p_\theta \Vert q)$ doublings per race. The minimax code is the bet that guarantees the smallest worst-case loss over every horse race in the family.

Universal coding for binary sequences

The problem. Encode a binary string $x^n \in \{0,1\}^n$ with no probabilistic assumption at all. The benchmark is hindsight: if the string has $k$ ones, the Bernoulli( $k/n$ ) Shannon code would spend $nH(k/n)$ bits. How close can a code that doesn’t know $k$ in advance get?

LemmaBinomial coefficient bounds (Wozencraft–Reiffen)

For $0 < k < n$ ,

$\sqrt{\frac{n}{8k(n-k)}}\; 2^{nH(k/n)} \;\le\; \binom{n}{k} \;\le\; \sqrt{\frac{n}{\pi k(n-k)}}\; 2^{nH(k/n)}$

(Proved as Lemma 17.5.1 in the book.)

Two-stage description (offline)

AlgorithmCount, then index

After reading the whole string:

Send $k = \sum_i x_i$ , using $\lceil \log(n+1) \rceil$ bits.
Send the index of $x^n$ among the $\binom{n}{k}$ strings with $k$ ones, using $\lceil \log \binom{n}{k} \rceil$ bits.

TheoremTwo-stage length

$l(x^n) \le \log(n+1) + \log\binom{n}{k} + 2 \le nH\!\left(\frac{k}{n}\right) + \frac{1}{2}\log n - \frac{1}{2}\log\!\left(\pi\,\frac{k}{n}\,\frac{n-k}{n}\right) + 3$

DerivationPlug in the upper binomial bound

Use $\log(n+1) \le \log n + 1$ and

$\log\binom{n}{k} \le nH\!\left(\frac kn\right) + \frac12\log\frac{n}{\pi k(n-k)} = nH\!\left(\frac kn\right) - \frac12\log n - \frac12\log\!\left(\pi\,\frac kn\,\frac{n-k}{n}\right)$

since $\frac{n}{k(n-k)} = \frac{1}{n\,(k/n)((n-k)/n)}$ . Add the pieces: the $\log n$ from the count and the $-\frac12\log n$ from the index leave $+\frac12\log n$ .

IntuitionHalf a log per parameter

The overhead over the hindsight-optimal $nH(k/n)$ is about $\frac{1}{2}\log n$ bits for the whole string, so $\frac{\log n}{2n} \to 0$ per symbol. Describing one real parameter ( $k/n$ ) to the precision the data can actually support costs about $\frac{1}{2}\log n$ bits.

WarningThe bound blows up at $k = 0$ or $k = n$

The last term is unbounded there. The actual length is then about $\log(n+1)$ bits, while $nH(0) = 0$ , so the redundancy is $\log n$ rather than $\frac{1}{2}\log n$ .

Mixture coding (online)

The problem. The two-stage code must see all of $x^n$ before sending anything. We want the same performance in one pass.

DefinitionUniform (Bayes) mixture of Bernoulli sources

Pretend the bias $\theta$ was drawn uniformly from $[0,1]$ . A specific sequence with $k$ ones then has probability

$q(x^n) = \int_0^1 \theta^k (1-\theta)^{n-k}\, d\theta = A(n,k)$

TheoremClosed form of the mixture

$A(n,k) = \frac{1}{(n+1)\binom{n}{k}}$

ProofIntegration by parts gives a recursion

Step 1: Integrate by parts with $u = (1-\theta)^{n-k}$ , $dv = \theta^k d\theta$ . The boundary term vanishes (for $k < n$ ), leaving

$A(n,k) = \frac{n-k}{k+1}\, A(n, k+1)$

Step 2: Base case. $A(n,n) = \int_0^1 \theta^n d\theta = \frac{1}{n+1}$ .

Step 3: Check the closed form satisfies the recursion. $\binom{n}{k+1} = \binom{n}{k}\frac{n-k}{k+1}$ , so $\frac{n-k}{k+1}\cdot\frac{1}{(n+1)\binom{n}{k+1}} = \frac{1}{(n+1)\binom nk}$ . ✓

∎

IntuitionThe mixture is the two-stage code

$\frac{1}{n+1}$ is the uniform probability of the count $k \in \{0, \ldots, n\}$ , and $\frac{1}{\binom nk}$ is the uniform probability of the index among strings with that count. So

$\log\frac{1}{q(x^n)} = \log(n+1) + \log\binom nk$

exactly the two-stage length without the ceilings. The mixture achieves the same $\approx \frac12\log n$ redundancy for every sequence, and it can be run online.

TheoremMixture code length

For every $x^n$ with $0 < k < n$ ,

$\log\frac{1}{q(x^n)} \le nH\!\left(\frac kn\right) + \frac{1}{2}\log n - \frac{1}{2}\log\!\left(\pi\,\frac kn\,\frac{n-k}{n}\right) + 2$

The Laplace estimator

TheoremSequential form of the mixture

Let $k_i$ be the number of ones among the first $i$ symbols. Then

$q(x_{i+1} = 1 \mid x^i) = \frac{q(x^i, 1)}{q(x^i)} = \frac{k_i + 1}{i + 2}$

ProofRatio of two mixture probabilities

$\frac{q(x^i,1)}{q(x^i)} = \frac{A(i+1, k_i+1)}{A(i, k_i)} = \frac{(i+1)\binom{i}{k_i}}{(i+2)\binom{i+1}{k_i+1}}$

and $\binom{i+1}{k_i+1} = \frac{i+1}{k_i+1}\binom{i}{k_i}$ , which leaves $\frac{k_i+1}{i+2}$ .

∎

IntuitionAdd one imaginary success and one imaginary failure

This is Laplace’s rule of succession (see conditional-probability-and-independence): the Bayesian posterior mean of $\theta$ under a uniform prior. It never predicts probability 0, so it never pays the infinite penalty of an “impossible” symbol. Feeding it to an arithmetic coder (Arithmetic coding) achieves $\log\frac{1}{q(x^n)}$ sequentially, with finite-precision arithmetic.

ImportantHorizon-free

The predictor $\frac{k_i+1}{i+2}$ doesn’t depend on $n$ . The coder needn’t know how long the message will be, which is exactly what a live telegraph line requires.

The Krichevsky–Trofimov estimator

WarningThe uniform prior underweights the extremes

At $k = 0$ or $k = n$ , $q(x^n) = \frac{1}{n+1}$ , so the redundancy is $\log(n+1)$ , not $\frac{1}{2}\log n$ . A uniform prior puts too little mass on $\theta$ near 0 and 1.

DefinitionDirichlet $(\frac12,\frac12)$ mixture

Weight $\theta$ by the Beta $(\frac12,\frac12)$ density $\frac{1}{\pi\sqrt{\theta(1-\theta)}}$ , which piles up near 0 and 1:

$q_{\frac12}(x^n) = \int_0^1 \theta^k(1-\theta)^{n-k}\,\frac{1}{\pi\sqrt{\theta(1-\theta)}}\,d\theta$

TheoremUniformly bounded redundancy

For all $x^n \in \{0,1\}^n$ , including $k = 0$ and $k = n$ ,

$\log\frac{1}{q_{\frac12}(x^n)} \le nH\!\left(\frac kn\right) + \frac12\log n + \log\frac{\pi}{\sqrt{8}}$

and the sequential predictor is

$q_{\frac12}(x_{i+1} = 1 \mid x^i) = \frac{k_i + \frac12}{i+1}$

NoteProof deferred

The book says the bound “can be shown” and analyzes the mixture in detail with universal portfolios (§16.7). The predictor adds half an imaginary success and half an imaginary failure, which is enough probability for all-zeros and all-ones strings.

Estimator	Prior on $\theta$	Next-symbol probability	Worst-case redundancy
Laplace	Uniform	$\frac{k_i+1}{i+2}$	$\log(n+1)$ (at $k = 0, n$ )
Krichevsky–Trofimov	Beta $(\frac12,\frac12)$	$\frac{k_i+\frac12}{i+1}$	$\frac12\log n + O(1)$ uniformly

Arithmetic coding

The problem. Huffman codes have integer codeword lengths, which can waste up to one bit per symbol. Coding blocks of $n$ symbols dilutes this to $1/n$ , but the codebook grows exponentially in $n$ . We want a code whose lengths are effectively fractional, that works incrementally symbol by symbol, and that can use a distribution learned on the fly (such as Laplace or KT).

The probability integral transform

Lemma $F(Y)$ is uniform

If $Y$ has a continuous distribution function $F$ , then $U = F(Y)$ is uniform on $[0,1]$ .

ProofInvert the CDF

$U \in [0,1]$ , and for $u \in [0,1]$ ,

$\Pr(U \le u) = \Pr(F(Y) \le u) = \Pr(Y \le F^{-1}(u)) = F(F^{-1}(u)) = u$

∎

NoteOn $F^{-1}$

The proof as written assumes $F$ is strictly increasing so that $F^{-1}$ exists. For a continuous but flat-in-places $F$ the result still holds, using the generalized inverse.

From sequences to numbers. Put “0.” in front of a sequence $x_1 x_2 \ldots$ over an alphabet of size $m+1$ and read it as a base- $(m+1)$ real number $X = 0.X_1X_2\ldots \in [0,1]$ . Its CDF is

$F_X(0.x_1x_2\ldots) = \Pr\{X_1 < x_1\} + \Pr\{X_1 = x_1, X_2 < x_2\} + \cdots$

ImportantCompression as “uniformizing”

If the distribution on infinite sequences has no atoms, then $U = F_X(X) = 0.F_1F_2\ldots$ is uniform on $[0,1]$ , so its binary digits $F_1, F_2, \ldots$ are i.i.d. fair bits. They are incompressible, and they determine the source sequence. The probability transform is a perfect compressor: it turns any atomless source into fair coin flips, the reverse of generation.

FormulaCDF of a binary sequence

For any binary process,

$F(x^n) = \sum_{k=1}^n p(x^{k-1}0)\, x_k$

Each one in the sequence adds the probability of the branch where that position was a zero instead.

ExampleBernoulli $(p)$ , sequence 110101

With $q = 1-p$ :

$F(110101) = \underbrace{q}_{X_1 < 1} + \underbrace{pq}_{X_2<1} + \underbrace{0}_{X_3<0} + \underbrace{p^2q\cdot q}_{X_4<1} + \underbrace{0}_{X_5<0} + \underbrace{p^2qpq\cdot q}_{X_6<1} = q + pq + p^2q^2 + p^3q^3$

Each term reuses the prefix probability computed for the previous one, so the work is linear in $n$ .

From intervals to codewords

IntuitionA sequence is a subinterval

The prefix $x^n$ corresponds to all infinite sequences starting with it. Under the probability transform, that set becomes an interval $[F(x^n), F(x^n) + p(x^n))$ of length exactly $p(x^n)$ . Any number in the interval identifies $x^n$ (given $n$ ). Shannon–Fano–Elias coding picks one with about $\log\frac{1}{p(x^n)} + 2$ bits.

AlgorithmArithmetic coding

Start with the interval $[0,1)$ .
For each new symbol, shrink the current interval to the sub-piece for that symbol, in proportion to its conditional probability given the past.
Whenever the top and bottom of the interval agree in their leading bits, those bits can no longer change. Output them, and rescale the interval to keep the arithmetic at fixed precision.
At the end, send enough bits to pin down a point inside the final interval.

The decoder runs the same subdivision and reads symbols off as the transmitted bits narrow down the interval. (Bell, Cleary and Witten give the fixed-precision details.)

ExampleTernary source, sequence ACAA

$p(A) = 0.4$ , $p(B) = 0.4$ , $p(C) = 0.2$ , so the symbol pieces are $A \to [0, 0.4)$ , $B \to [0.4, 0.8)$ , $C \to [0.8, 1)$ .

After	Interval	Width
—	$[0, 1)$	1
`A`	$[0, 0.4)$	0.4
`AC`	$[0.32, 0.4)$	0.08
`ACA`	$[0.32, 0.352)$	0.032
`ACAA`	$[0.32, 0.3328)$	0.0128

The final width is $p(ACAA) = 0.4 \cdot 0.2 \cdot 0.4 \cdot 0.4 = 0.0128$ . Encode the midpoint $0.3264 = 0.010100111_2$ with $\lceil\log\frac{1}{0.0128}\rceil + 2 = 9$ bits.

TheoremArithmetic coding length

For any $n$ and any (possibly learned) distribution $q$ on sequences, arithmetic coding encodes $x^n$ in at most $\log\frac{1}{q(x^n)} + 2$ bits. With $q = p$ for an i.i.d. source, the expected length is within 2 bits of $H(X_1, \ldots, X_n)$ for the whole block.

RemarkNot optimal for a fixed block, but incremental

For any fixed $n$ , a Huffman code on $n$ -blocks could do slightly better on average. But arithmetic coding needs no codebook, extends to any block length, and lets $q$ change with every symbol. Combined with the Laplace or KT predictor, it gives a universal one-pass coder for binary sources.

Lempel–Ziv coding

IntuitionTelegraph codebooks were dictionary compression

When telegrams were charged per word, large companies printed private codebooks that mapped frequent phrases to short code words. Indian greetings telegrams worked the same way: “25” meant Merry Christmas, and “26” meant May Heaven’s choicest blessings be showered on the newly married couple. The sender paid for a number; the destination office printed the sentence. These dictionaries were fixed and agreed in advance.

Ziv and Lempel’s idea (1977, 1978) was an adaptive dictionary that both ends build from the message itself as it passes. A phrase that has already appeared is replaced by a pointer to where it appeared. Nothing about the source distribution is needed.

Version	Also called	Dictionary	Used in
LZ77	sliding-window LZ, LZ1	Every substring in a window of past symbols	gzip, pkzip
LZ78	tree-structured LZ, LZ2	The phrases parsed so far, arranged as a tree	Unix `compress`, modems, GIF (via LZW)

Sliding-window Lempel–Ziv (LZ77)

DefinitionParsing

A parsing of $x_1x_2\cdots x_n$ divides the string into phrases separated by commas.

AlgorithmLZ77 (Storer–Szymanski variant), window $W$

Suppose everything up to time $i-1$ has been encoded.

Find the largest $k$ such that, for some $j$ with $i-1-W \le j \le i-1$ , the length- $k$ string starting at $x_j$ equals the length- $k$ string starting at $x_i$ .
If a match exists, emit $(F{=}1, P, L)$ : a flag, the match’s position $P$ (counted back from the end of the window), and its length $L = k$ .
Otherwise emit $(F{=}0, C)$ , the raw character $C$ .
Advance by the phrase length and repeat.

WarningMatches may overlap the phrase being encoded

The match must start in the window but may run past it into the new phrase. Copying from just behind the cursor reproduces runs: in the example below, ABBABB is copied from a match three symbols back. In theory such a match is unbounded; in practice the maximum phrase length is capped.

Example $W = 4$ , string ABBABBABBBAABABA

Parsing: A, B, B, ABBABB, BA, A, BA, BA

Pointers: (0,A), (0,B), (1,1,1), (1,3,6), (1,4,2), (1,1,1), (1,3,2), (1,2,2)

The fourth phrase copies 6 symbols from a match starting 3 back, a self-overlapping copy. Encoding a one-symbol match as $(1,1,1)$ can cost more than sending the raw character; practical coders send short matches raw (Problem 13.8).

IntuitionThe dictionary is the recent past

The implicit dictionary is every substring of the last $W$ symbols plus all single characters. Each step sends a pointer to the longest dictionary entry that matches what comes next. Frequent strings are likely to be found recently and long, so they cost little.

Tree-structured Lempel–Ziv (LZ78)

AlgorithmLZ78 incremental parsing

Repeatedly cut off the shortest phrase not seen before. Since it is the shortest new phrase, all its prefixes have already appeared, in particular the phrase minus its last symbol. Encode each phrase as (index of that prefix phrase, last symbol), with index 0 for the empty prefix.

ExampleString ABBABBABBBAABABAA…

#	Phrase	Prefix phrase	Code
1	`A`	empty	(0, A)
2	`B`	empty	(0, B)
3	`BA`	2 (`B`)	(2, A)
4	`BB`	2 (`B`)	(2, B)
5	`AB`	1 (`A`)	(1, B)
6	`BBA`	4 (`BB`)	(4, A)
7	`ABA`	5 (`AB`)	(5, A)
8	`BAA`	3 (`BA`)	(3, A)

flowchart TD
  R(("root")) -->|A| P1["1: A"]
  R -->|B| P2["2: B"]
  P1 -->|B| P5["5: AB"]
  P5 -->|A| P7["7: ABA"]
  P2 -->|A| P3["3: BA"]
  P2 -->|B| P4["4: BB"]
  P3 -->|A| P8["8: BAA"]
  P4 -->|A| P6["6: BBA"]

RemarkLZW

Sending a raw character with every phrase wastes bits. Welch’s variant treats the last character of each phrase as the first character of the next, so each phrase is sent as a single index. LZW is the basis of Unix compress, modem compression, and GIF.

Optimality of Lempel–Ziv algorithms

Both versions are universal: for any stationary ergodic source, their compression rate converges to the entropy rate $H(\mathcal{X})$ , though they never estimate the source distribution. The two proofs work very differently.

	LZ77	LZ78
Key idea	Frequent strings recur soon, so pointers are short	A string with many distinct phrases can’t be very probable
Key lemma	Kac’s recurrence lemma	Ziv’s inequality
Proved here	A simplified “infinite past” version	The actual algorithm

LZ77 via recurrence times

The simplified algorithm. Assume a stationary ergodic process $\ldots, X_{-1}, X_0, X_1, \ldots$ , and that encoder and decoder both see the infinite past. To send the block $X_0^{n-1} = (X_0, \ldots, X_{n-1})$ , send only how far back it last occurred:

$R_n(X_0^{n-1}) = \min\{\, j > 0 : (X_{-j}, \ldots, X_{-j+n-1}) = (X_0, \ldots, X_{n-1}) \,\}$

The decoder looks back $R_n$ symbols and copies. The cost is the cost of describing the integer $R_n$ .

LemmaA prefix code for the positive integers

There is a prefix-free code for the integers in which $k$ has length $\log k + 2\log\log k + O(1)$ .

ProofSend the length of the length

Step 1: A crude code. $C_1(k)$ = $\lfloor\log k\rfloor$ zeros, then $k$ in binary. The binary form of $k$ starts with a 1, so the decoder counts zeros, learns how many digits follow, and reads them. Length $2\lfloor\log k\rfloor + 1 \le 2\log k + 3$ . It’s prefix-free, but the unary length prefix doubles the cost.

Step 2: Encode the length with $C_1$ , not in unary. Send the number of binary digits of $k$ using $C_1$ , which costs about $2\log\log k$ bits, then send $k$ in binary, about $\log k$ bits. The total is less than $\log k + 2\log\log k + 4$ .

∎

IntuitionWhy the overhead must grow at all

With no upper limit on $k$ known in advance, the receiver must be told where the number ends. The $2\log\log k$ term is the price of that punctuation, negligible next to $\log k$ .

LemmaKac’s lemma

Let $\ldots, U_{-1}, U_0, U_1, \ldots$ be stationary ergodic on a countable alphabet, and $p(u) > 0$ . Let

$Q_u(i) = \Pr\{U_{-i} = u,\ U_j \ne u \text{ for } -i < j < 0 \mid U_0 = u\}$

be the conditional probability that the most recent earlier occurrence of $u$ was $i$ steps back. Then

$\mathbb{E}[R_1 \mid U_0 = u] = \sum_i i\,Q_u(i) = \frac{1}{p(u)}$

IntuitionWaiting time is reciprocal frequency

For an i.i.d. process the look-back time is geometric with parameter $p(u)$ , with mean $1/p(u)$ . Kac says the same holds for any stationary ergodic process. The heuristic: in a sample of length $n$ , $u$ appears about $np(u)$ times, so the average gap between appearances is $n/(np(u)) = 1/p(u)$ .

ProofDecompose by the last occurrence before 0 and the first at or after 0

Step 1: A partition. For $j \ge 1$ , $k \ge 0$ let

$A_{jk} = \{U_{-j} = u,\ U_l \ne u \text{ for } -j < l < k,\ U_k = u\}$

“the last $u$ before time 0 is at $-j$ , and the first $u$ at or after time 0 is at $k$ ”. These events are disjoint. By ergodicity, $u$ occurs both before and after 0 almost surely, so $\Pr\{\bigcup_{j,k} A_{jk}\} = 1$ .

Step 2: Add up.

$1 = \sum_{j \ge 1}\sum_{k \ge 0} \Pr(U_k = u)\, \Pr\{U_{-j} = u,\ U_l \ne u,\ -j<l<k \mid U_k = u\}$

Step 3: Stationarity. Shift time by $-k$ : the conditional probability is a gap of $j+k$ ending at an occurrence of $u$ , i.e. $Q_u(j+k)$ , and $\Pr(U_k = u) = p(u)$ . So

$1 = p(u)\sum_{j \ge 1}\sum_{k \ge 0} Q_u(j+k)$

Step 4: Count pairs. For each $i \ge 1$ there are exactly $i$ pairs $(j,k)$ with $j \ge 1$ , $k \ge 0$ , $j+k = i$ . So $1 = p(u)\sum_i i\,Q_u(i)$ .

∎

RemarkAn amusing consequence

Averaging over the symbol, $\mathbb{E}R_1 = \sum_u p(u)\cdot\frac{1}{p(u)} = m$ , the number of symbols with positive probability, regardless of the distribution.

CorollaryRecurrence of blocks

Apply Kac to the block process $U_i = (X_i, \ldots, X_{i+n-1})$ , which is also stationary ergodic:

$\mathbb{E}\big[R_n \mid X_0^{n-1} = x_0^{n-1}\big] = \frac{1}{p(x_0^{n-1})}$

TheoremRecurrence-time coding achieves the entropy rate

Let $L_n = \log R_n + 2\log\log R_n + O(1)$ be the description length of $X_0^{n-1}$ . Then

$\frac{1}{n}\mathbb{E}\,L_n \longrightarrow H(\mathcal{X})$

ProofLower bound from source coding, upper bound from Jensen and Kac

Lower bound. This is a prefix code for the block, so $\mathbb{E}L_n \ge H(X_0^{n-1}) \ge nH(\mathcal{X})$ (for a stationary source the block average of entropies is at least the rate).

Step 1: Main term. Condition on the block, then apply Jensen (log is concave) and Kac:

$\frac1n\mathbb{E}\log R_n = \frac1n\sum_{x_0^{n-1}} p(x_0^{n-1})\,\mathbb{E}\big[\log R_n \mid x_0^{n-1}\big] \le \frac1n\sum p(x_0^{n-1})\log\frac{1}{p(x_0^{n-1})} = \frac{1}{n}H(X_0^{n-1}) \rightarrow H(\mathcal{X})$

Step 2: The $\log\log$ term vanishes. By Jensen again and Step 1,

$\frac1n\mathbb{E}\log\log R_n \le \frac1n\log\mathbb{E}\log R_n \le \frac1n\log H(X_0^{n-1})$

For large $n$ , $H(X_0^{n-1}) < n(H + \epsilon)$ , so this is at most $\frac{1}{n}\log n + \frac{1}{n}\log(H+\epsilon) \rightarrow 0$ .

∎

IntuitionPoint to the past instead of describing the present

A typical block has probability about $2^{-nH}$ , so by Kac it last occurred about $2^{nH}$ steps ago. Writing down that distance takes about $nH$ bits. Matching the past is as good as knowing the distribution.

WarningNot a practical algorithm

With entropy rate $\frac12$ and a 200-bit block, you’d look back on average $2^{100} \approx 10^{30}$ bits. The practical finite-window LZ77 is also asymptotically optimal by similar ideas (Wyner–Ziv), but the book doesn’t give that proof. Ziv and Lempel’s original paper showed the finite-window version beats any finite-state compressor on every individual sequence.

LZ78 via distinct parsings

LZ78 emits $c(n)$ pairs (pointer, last bit), each pointer using $\log c(n)$ bits, so its length is

$l(x^n) = c(n)\big(\log c(n) + 1\big)$

We show $\frac{c(n)\log c(n)}{n} \rightarrow H(\mathcal{X})$ at most.

DefinitionDistinct parsing

A parsing is distinct if no two phrases are identical. For example, 0,111,1 is a distinct parsing of 01111; 0,11,11 is not. LZ78 always produces a distinct parsing.

IntuitionThe two ingredients

Not many phrases. There are only $2^l$ binary strings of length $l$ , so a distinct parsing can’t have too many short phrases. The count is at most about $n/\log n$ .
Many distinct phrases means low probability. For an i.i.d. source on $\{A,B,C,D\}$ , $P(DABC) = p_Dp_Ap_Bp_C \le \frac{1}{256}$ (maximized when all four are equal). $P(ABAB)$ can reach $\frac{1}{16}$ , and $P(AAAA)$ can reach 1. A sequence built from many distinct pieces can’t be very likely. Ziv’s inequality extends this to phrases and Markov sources.

So strings with few phrases compress well (and may be likely), and strings with many phrases compress badly but must be unlikely. On average, the two balance at the entropy rate.

LemmaFew phrases in a distinct parsing (Lempel–Ziv)

The number of phrases in any distinct parsing of a binary string of length $n$ satisfies

$c(n) \le \frac{n}{(1 - \epsilon_n)\log n}, \qquad \epsilon_n = \min\left\{1,\ \frac{\log(\log n) + 4}{\log n}\right\} \rightarrow 0$

ProofUse the shortest phrases possible

Step 1: Total length of all strings up to length $k$ .

$n_k = \sum_{j=1}^k j\,2^j = (k-1)2^{k+1} + 2$

Step 2: The count is largest when phrases are short. If $n = n_k$ , the most phrases come from using every string of length $\le k$ once:

$c(n_k) \le \sum_{j=1}^k 2^j = 2^{k+1} - 2 < 2^{k+1} \le \frac{n_k}{k-1}$

Step 3: In between. For $n_k \le n < n_{k+1}$ , write $n = n_k + \Delta$ . The extra $\Delta$ symbols form at most $\Delta/(k+1)$ phrases of length $k+1$ , so

$c(n) \le \frac{n_k}{k-1} + \frac{\Delta}{k+1} \le \frac{n}{k-1}$

Step 4: Relate $k$ to $n$ . From $n \ge n_k \ge 2^k$ , $k \le \log n$ . From $n \le n_{k+1} \le (\log n + 2)2^{k+2}$ , $k + 2 \ge \log\frac{n}{\log n + 2}$ , which for $n \ge 4$ gives

$k - 1 \ge \log n - \log(\log n + 2) - 3 \ge \left(1 - \frac{\log\log n + 4}{\log n}\right)\log n = (1-\epsilon_n)\log n$

Substitute into Step 3.

∎

LemmaGeometric maximizes entropy at fixed mean

A nonnegative integer random variable $Z$ with mean $\mu$ has

$H(Z) \le (\mu+1)\log(\mu+1) - \mu\log\mu$

ProofRelative entropy to the geometric

The book cites the maximum entropy theorem (Theorem 12.1.1). A direct argument: let $g(z) = (1-r)r^z$ with $r = \frac{\mu}{\mu+1}$ , the geometric with mean $\mu$ . Then $0 \le D(p_Z \Vert g) = -H(Z) - \sum_z p_Z(z)\log g(z)$ , so

$H(Z) \le -\log(1-r) - \mu\log r = \log(\mu+1) - \mu\log\frac{\mu}{\mu+1} = (\mu+1)\log(\mu+1) - \mu\log\mu$

∎

Markov approximations. Let $\{X_i\}$ be a binary stationary ergodic process with law $P$ . For fixed $k$ , its $k$ -th-order Markov approximation is

$Q_k(x_{-(k-1)}, \ldots, x_n) = P\big(x_{-(k-1)}^0\big)\prod_{j=1}^n P\big(x_j \mid x_{j-k}^{j-1}\big)$

with the initial state $x_{-(k-1)}^0$ part of the specification. By the ergodic theorem,

$-\frac{1}{n}\log Q_k\big(X_1, \ldots, X_n \mid X_{-(k-1)}^0\big) = -\frac{1}{n}\sum_{j=1}^n\log P\big(X_j \mid X_{j-k}^{j-1}\big) \longrightarrow H\big(X_j \mid X_{j-k}^{j-1}\big)$

and $H(X_j \mid X_{j-k}^{j-1}) \downarrow H(\mathcal{X})$ as $k \rightarrow \infty$ (monotone conditional entropies).

Bookkeeping. Parse $x_1^n$ into distinct phrases $y_1, \ldots, y_c$ . Let $s_i$ be the $k$ bits just before phrase $y_i$ (its state), and let $c_{ls}$ count the phrases of length $l$ with preceding state $s$ . Then

$\sum_{l,s} c_{ls} = c, \qquad \sum_{l,s} l\, c_{ls} = n$

LemmaZiv’s inequality

For any distinct parsing of $x_1x_2\cdots x_n$ ,

$\log Q_k(x_1, \ldots, x_n \mid s_1) \le -\sum_{l,s} c_{ls}\log c_{ls}$

The right side doesn’t depend on $Q_k$ at all.

ProofGroup phrases by (length, state), then Jensen

Step 1: Factor by phrases. By the Markov property, $Q_k(x_1^n \mid s_1) = \prod_{i=1}^c P(y_i \mid s_i)$ , so

$\log Q_k = \sum_{l,s}\ \sum_{i:\, |y_i| = l,\ s_i = s}\log P(y_i \mid s_i)$

Step 2: Jensen within each group. Write each inner sum as $c_{ls}$ times an average, and use concavity of $\log$ :

$\sum_{i \in \text{group}}\log P(y_i \mid s_i) = c_{ls}\cdot\frac{1}{c_{ls}}\sum\log P(y_i\mid s_i) \le c_{ls}\log\left(\frac{1}{c_{ls}}\sum_{i \in \text{group}} P(y_i \mid s_i)\right)$

Step 3: Distinctness caps the inner sum. Within a group, the phrases are distinct strings of the same length $l$ , all conditioned on the same state $s$ . They are disjoint outcomes of one conditional distribution, so $\sum P(y_i \mid s) \le 1$ . Hence each group contributes at most $c_{ls}\log\frac{1}{c_{ls}}$ .

∎

IntuitionProbability bounded by pure combinatorics

The left side is a probability under the source. The right side depends only on how the string happened to parse. Distinctness is the whole engine: $c_{ls}$ different strings competing for at most one unit of probability can’t each get more than about $1/c_{ls}$ .

TheoremPhrase count is controlled by the entropy rate

For a binary stationary ergodic process, with probability 1,

$\limsup_{n\rightarrow\infty}\frac{c(n)\log c(n)}{n} \le H(\mathcal{X})$

ProofTurn Ziv’s inequality into an entropy of phrase statistics

Step 1: Normalize the counts. With $\pi_{ls} = c_{ls}/c$ ,

$-\sum c_{ls}\log c_{ls} = -\sum c\,\pi_{ls}\log(c\,\pi_{ls}) = -c\log c + c\,H(U,V)$

where $(U, V)$ has $\Pr(U = l, V = s) = \pi_{ls}$ , and $\mathbb{E}U = n/c$ . Ziv’s inequality becomes

$\frac{c}{n}\log c \le -\frac1n\log Q_k(x_1^n \mid s_1) + \frac{c}{n}H(U,V)$

Step 2: Bound $H(U,V)$ . $H(U,V) \le H(U) + H(V)$ . The state $V$ is $k$ bits, so $H(V) \le k$ . By the geometric lemma with $\mu = n/c$ ,

$H(U) \le \log\frac{n}{c} + \left(\frac nc + 1\right)\log\left(\frac cn + 1\right)$

so $\frac{c}{n}H(U,V) \le \frac cn k + \frac cn\log\frac nc + o(1)$ .

Step 3: Every correction term vanishes. By the phrase-count lemma, $c/n \le (1+o(1))/\log n \rightarrow 0$ . Since $x\log\frac1x \rightarrow 0$ as $x \rightarrow 0$ , $\frac cn\log\frac nc = O\!\left(\frac{\log\log n}{\log n}\right) \rightarrow 0$ . So $\frac cn H(U,V) \rightarrow 0$ .

Step 4: Ergodic limit, then $k \rightarrow \infty$ . With probability 1,

$\limsup\frac{c\log c}{n} \le \lim -\frac1n\log Q_k = H\big(X_0 \mid X_{-1}, \ldots, X_{-k}\big)$

This holds for every $k$ , and the right side tends to $H(\mathcal{X})$ .

∎

TheoremLZ78 is asymptotically optimal

For a binary stationary ergodic process,

$\limsup_{n\rightarrow\infty}\frac1n\, l(X_1, \ldots, X_n) \le H(\mathcal{X}) \qquad \text{with probability 1}$

ProofAdd the last-bit term

$\frac{l}{n} = \frac{c\log c}{n} + \frac cn$ . The first term has $\limsup \le H(\mathcal{X})$ by the theorem above, and $\frac cn \rightarrow 0$ by the phrase-count lemma.

∎

RemarkWhat the proof didn’t use

The phrase-count bound and Ziv’s inequality hold for any distinct parsing, not just LZ78’s incremental one. The argument extends to many parsing variants, including multiple context-dependent trees. And the code never looked at $P$ : it is a universal code that reaches the entropy rate of whatever stationary ergodic source happens to be on the line.

Quick reference

Object	Statement	Reads as
Redundancy	$R(p_\theta, q) = D(p_\theta \Vert q)$	Extra bits for coding with $q$ .
Minimax redundancy	$R^* = \min_q\max_\theta D(p_\theta\Vert q)$	Radius of the smallest information ball.
Gallager–Ryabko	$R^* = C = \max_\pi I(\theta;X)$ ; $q^* = q_{\pi^*}$	The price of not knowing is a channel capacity.
Centroid identity	$\sum_i\pi_iD(p_i\Vert q) = I_\pi + D(q_\pi\Vert q)$	Parallel-axis theorem for relative entropy.
Erasure example	$R^* = 1 - \alpha$	Midpoint distribution is the universal code.
Two-stage / mixture	$\le nH(k/n) + \frac12\log n + O(1)$	Half a log per parameter.
Uniform mixture	$q(x^n) = \frac{1}{(n+1)\binom nk}$	Count, then index.
Laplace	$\frac{k_i+1}{i+2}$	One pseudo-success, one pseudo-failure.
KT	$\frac{k_i+\frac12}{i+1}$ ; uniform $\frac12\log n + O(1)$	Fixes the all-zeros/all-ones case.
Probability transform	$F(Y)$ uniform	Optimal compression produces fair bits.
Binary CDF	$F(x^n) = \sum_k p(x^{k-1}0)\,x_k$	Computed incrementally.
Arithmetic coding	$\le \log\frac{1}{q(x^n)} + 2$ bits	Shrinking intervals, any $q$ , one pass.
LZ77	pointer $(P, L)$ into a window	gzip.
LZ78	(prefix index, last symbol)	compress, GIF.
Integer code	$\log k + 2\log\log k + O(1)$	Send the length of the length.
Kac	$\mathbb{E}[R_1\mid U_0 = u] = 1/p(u)$	Waiting time is reciprocal frequency.
LZ77 (infinite past)	$\frac1n\mathbb{E}L_n \rightarrow H(\mathcal{X})$	Point to where it last occurred.
Phrase count	$c(n) \le \frac{n}{(1-\epsilon_n)\log n}$	Few distinct short strings.
Ziv’s inequality	$\log Q_k \le -\sum c_{ls}\log c_{ls}$	Many distinct phrases means low probability.
LZ78	$\limsup\frac{l}{n} \le H(\mathcal{X})$ a.s.	Universal.

Facts to keep to hand

Every universal-coding cost is a relative entropy. Coding with $q$ against source $p$ costs $D(p\Vert q)$ . The best single $q$ for a family is the centroid of the capacity-achieving mixture, and its worst-case cost is the capacity of the channel from parameter to symbol.
Mixtures learn. A Bayesian mixture over the family is a predictor (Laplace, KT), and an arithmetic coder turns any predictor into a code of length $\log\frac{1}{q(x^n)} + 2$ . Learning the parameter costs about $\frac12\log n$ bits in total.
Arithmetic coding separates modelling from coding. The coder is fixed; all the intelligence is in $q$ . The same split appears in the gambler-twin compressor.
Lempel–Ziv needs no model at all. LZ77 works because recent strings recur after about $1/p$ steps (Kac); LZ78 because distinct phrases can’t all be likely (Ziv). Both reach the entropy rate of any stationary ergodic source.
Asymptotic optimality is not finite- $n$ optimality. Overheads such as $\log\log$ , $c/n$ and $\frac12\log n$ vanish only per symbol and slowly. The idealized infinite-past LZ77 is wildly impractical.

References

Cover & Thomas, Elements of Information Theory — Chapter 13

Related