Universal coding asks for one code that performs well for many possible sources. The mathematical object is regret or redundancy relative to the best code that knew the source.
Pointwise regret
Definition. For a model class \(\mathcal P\) on \(\mathcal X^n\) and coding distribution \(Q_n\), the pointwise regret is \[ \sup_{x^n}\left\{-\log Q_n(x^n)-\inf_{P\in\mathcal P}[-\log P(x^n)]\right\}. \]
Normalized maximum likelihood
Proposition. If \[ S_n=\sum_{x^n}\sup_{P\in\mathcal P}P(x^n)<\infty, \] then the normalized maximum likelihood law \[ Q_n^\star(x^n)=\frac{\sup_{P\in\mathcal P}P(x^n)}{S_n} \] has minimax pointwise regret \(\log S_n\).
Proof by domination
Proof. For any \(Q_n\), the worst-case regret is at least \(r\) only if \(Q_n(x^n)\ge e^{-r}\sup_P P(x^n)\) for all \(x^n\). Summing over \(x^n\) gives \(1\ge e^{-r}S_n\), hence \(r\ge\log S_n\). The normalized maximum likelihood distribution attains equality.
Asymptotic parametric scale
Remark. For regular \(d\)-dimensional parametric families, minimax redundancy often grows like \((d/2)\log n\) plus lower-order constants. The main lesson is not the constant but the statistical dimension penalty.
Universal codes
Definition. A sequence of coding laws \(Q_n\) is universal for class \(\mathcal P\) if \[ \frac1nD(P^n\|Q_n)\to0 \] for every \(P\in\mathcal P\), or uniformly if the supremum over \(P\) tends to zero.
Bayesian mixtures
Definition. Given prior \(\pi\) on \(\Theta\), \[ Q_\pi(x^n)=\int P_\theta(x^n)\,\pi(\mathrm{d}\theta). \]
Proposition. For any measurable neighborhood \(B\subseteq\Theta\), \[ -\log Q_\pi(x^n) \le-\log\inf_{\theta\in B}P_\theta(x^n) +\log\frac1{\pi(B)}. \]
Proof. \(Q_\pi(x^n)\ge\int_BP_\theta(x^n)\pi(\mathrm{d}\theta) \ge\pi(B)\inf_{\theta\in B}P_\theta(x^n)\). Take negative logarithms.
Krichevsky-Trofimov code
Example. For binary iid data with \(k\) ones, use the Jeffreys mixture \[ Q_{\mathrm{KT}}(x^n)= \int_0^1p^k(1-p)^{n-k} \frac{p^{-1/2}(1-p)^{-1/2}}{\pi}\,\mathrm{d}p. \] Sequentially, \[ Q(X_{t+1}=1\mid X^t)= \frac{k_t+1/2}{t+1}. \] Its worst-case regret is \(\tfrac12\log n+O(1)\), matching the one-dimensional parametric order.
Normalized maximum likelihood
Definition. If the Shtarkov sum \[ C_n=\sum_{x^n}\sup_{\theta}P_\theta(x^n) \] is finite, normalized maximum likelihood is \[ Q_{\mathrm{NML}}(x^n)= \frac{\sup_\theta P_\theta(x^n)}{C_n}. \]
Theorem. NML uniquely minimizes worst-case pointwise regret, and \[ \inf_Q\sup_{x^n} \log\frac{\sup_\theta P_\theta(x^n)}{Q(x^n)} =\log C_n. \]
Proof. NML makes the regret constant \(\log C_n\). For arbitrary \(Q\), if every regret were below \(\log C_n\), then \(Q(x^n)>\sup_\theta P_\theta(x^n)/C_n\) for every sequence; summing would give \(\sum Q>1\), a contradiction.
Minimax expected redundancy and channel capacity
Theorem. Under finite or compact regular conditions, \[ \inf_Q\sup_{\theta}D(P_\theta^n\|Q) = \sup_{\pi}I_\pi(\Theta;X^n). \]
Proof. For any prior \(\pi\) and law \(Q\), \[ \int D(P_\theta^n\|Q)\,\pi(\mathrm{d}\theta) =I_\pi(\Theta;X^n)+D(P_\pi^n\|Q). \] Minimizing the average over \(Q\) chooses the mixture \(P_\pi^n\) and leaves mutual information. A minimax theorem exchanges infimum and supremum.
Regular parametric asymptotics
Theorem. For a regular \(d\)-dimensional iid family on compact \(\Theta\), \[ \log C_n= \frac d2\log\frac{n}{2\pi} +\log\int_\Theta\sqrt{\det I(\theta)}\,\mathrm{d}\theta +o(1), \] under conditions making NML finite. Jeffreys mixture has the same leading minimax redundancy.
Proof outline. Group sequences by their MLE and apply a local quadratic likelihood expansion. Parameter cells of diameter \(n^{-1/2}\) contribute Fisher-volume element \(\sqrt{\det I(\theta)}\,\mathrm{d}\theta\), while Gaussian integration contributes \((n/2\pi)^{d/2}\). Laplace approximation of Jeffreys mixture yields the same local normalization.
Context-tree weighting
For finite-memory binary sources with unknown context tree, context-tree weighting recursively mixes the hypotheses that a node is a leaf or splits into children. It computes an exact Bayesian mixture over exponentially many trees in linear time and achieves redundancy near the best tree plus a model-complexity penalty.
Lempel-Ziv universality
Theorem. For every stationary ergodic finite-alphabet source, Lempel-Ziv code length satisfies \[ \frac1nL_{\mathrm{LZ}}(X^n)\to\overline H(X) \quad\text{almost surely}. \]
Proof outline. Parse the sequence into distinct phrases. Combinatorial bounds relate phrase count to code length, while recurrence properties of stationary ergodic processes control phrase lengths by entropy rate. Kraft's inequality supplies the converse lower limit; the parsing construction gives the upper limit.
Minimum description length
MDL selects the model minimizing total description length. Refined MDL uses NML or luckiness-normalized variants rather than an arbitrary two-part parameter code. Its complexity penalty is determined by the model's distinguishable distributions, not simply raw parameter count; singular models require different asymptotics from regular \(d\log n/2\).