Module 10. Algorithmic Information Theory: Shortest Descriptions, MDL, and Universal Prediction — exercises and worked solutions · Information Theory for ML

Exercise 1. How many strings can be compressed?

For a fixed universal prefix machine, show that among $n$ -bit strings the fraction satisfying

K(x)<n-c

is smaller than $2^{-c}$ .

How many binary programs have length below $n-c$ ?
Why can one halting program not describe two different strings?
How does the argument change for plain complexity $C(x)$ ?

Show answer and solution

The number of binary programs of length strictly below $n-c$ is

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

A prefix machine may accept fewer programs, since not every bit string must be a valid halting program.

For a fixed deterministic machine, one halting program has at most one finite output. Therefore fewer than $2^{n-c}$ distinct $n$ -bit strings satisfy

K(x)<n-c.

Dividing by the total number $2^n$ gives

\frac{ \#\{x\in\{0,1\}^n:K(x)<n-c\} }{2^n} < 2^{-c}.

Thus

\boxed{ \Pr_{X\sim U_n}[K(X)<n-c]<2^{-c} }.

The counting step itself uses only the number of binary programs and the fact that a deterministic program has at most one finite output. Prefix-freeness matters for the chosen definition of $K$ , for Kraft's inequality, and for the later weights $2^{-|p|}$ .

The same elementary counting argument applies to plain complexity $C(x)$ . Prefix versus plain complexity matters elsewhere—for self-delimitation, chain rules, and algorithmic probability.

Exercise 2. A short generator and poor practical compression

Consider $N$ bytes generated by a deterministic PRNG from a fixed seed.

Give an upper bound on $K(x)$ using the generator program, the seed, and a description of $N$ .
Explain why gzip may still return almost $8N$ bits.
Why does this not mean that gzip failed at its own objective?
What side information must the decoder receive to use the short generative description?

Show answer and solution

Let $G$ be a fixed PRNG implementation, $s$ its seed, and $N$ the requested output length. A program for $x$ can contain

a description of $G$ ;
the seed $s$ ;
a self-delimiting description of $N$ ;
the instruction “generate the first $N$ bytes.”

Hence

\boxed{ K(x) \le K(G)+K(s)+K(N)+O(1) }.

For fixed $G$ and $s$ , this grows only as $O(\log N)$ while the object length is $8N$ bits.

Gzip may nevertheless fail to compress the stream because it searches for dictionaries, repetitions, and local statistical patterns of a particular kind. A good PRNG is designed to look random to broad classes of bounded tests. The short rule “run $G$ with seed $s$ ” exists, but gzip does not search arbitrary programs.

This is not a failure relative to gzip's own objective. Gzip finds a good code in a fixed format and model family under resource constraints; it does not compute the uncomputable quantity $K(x)$ .

To exploit the generative description, the decoder must know the exact PRNG implementation and version, the seed, $N$ , the byte-generation convention, and any platform-dependent semantics. All of these contribute to total description length.

A short description also does not imply fast decoding. The definition of $K(x)$ does not charge for runtime, so a shortest program may take an enormous amount of time.

Exercise 3. Entropy and expected Kolmogorov complexity

Let

P= \left( \frac12, \frac14, \frac18, \frac18 \right).

Compute $H_2(P)$ .
Explain why $H_2(P)\le\mathbb E_P K(X)$ for prefix complexity.
If describing the distribution costs $K(P)=40$ bits, what upper bound follows from
$\mathbb E K(X) \le H_2(P)+K(P)+O(1)?$
Why does the bound become more informative for a block of $n$ i.i.d. observations? What extra cost is needed to describe $n$ ?

Show answer and solution

For

P=\left(\frac12,\frac14,\frac18,\frac18\right),

\begin{aligned} H_2(P) &= -\frac12\log_2\frac12 -\frac14\log_2\frac14 -2\cdot\frac18\log_2\frac18\\ &= \frac12+\frac12+2\cdot\frac38\\ &= \boxed{1.75\text{ bits}}. \end{aligned}

Shortest prefix programs form a prefix code for the possible outcomes. The expected length of any prefix code is at least entropy, so

H_2(P) \le \mathbb E_P K(X).

If $K(P)=40$ bits, then

\mathbb E K(X) \le 1.75+40+O(1) = \boxed{41.75+O(1)\text{ bits}}.

For one draw from a four-symbol alphabet, this is extremely loose because model cost dominates. For an i.i.d. block, the decoder must also know the block length. A more explicit bound is

\mathbb E K(X_{1:n}) \le nH_2(P)+K(P)+K(n)+O(1),

where $K(n)=O(\log n)$ . Therefore

\frac1n\mathbb E K(X_{1:n}) \le 1.75+\frac{40+O(\log n)}{n}.

The fixed model cost vanishes per observation.

A single observation does not identify a unique distribution $P$ : infinitely many distributions assign positive probability to the same outcome. Describing one object and predicting future data are therefore different requirements.

Exercise 4. The MDL switching point

Two models have description lengths

L(h_A)=40\ \text{bits}, \qquad L(h_B)=220\ \text{bits}.

Their average data-code lengths per object are

\ell_A=0.76\ \text{bits}, \qquad \ell_B=0.61\ \text{bits}.

Write the total lengths for a dataset of size $n$ .
What is the smallest $n$ for which model $B$ is shorter?
Explain why this illustrates the dependence of admissible model complexity on data volume.
What changes if $L(h)$ depends on parameter precision?

Show answer and solution

The total lengths are

L_A(n)=40+0.76n,

L_B(n)=220+0.61n.

Model $B$ wins when

220+0.61n < 40+0.76n,

so

180<0.15n,

n>1200.

At $n=1200$ , both descriptions are $952$ bits. The smallest integer sample size for which $B$ is strictly shorter is

\boxed{n=1201}.

The more complex model pays an additional $180$ bits once, but saves $0.15$ bit per observation. Small datasets favor model cost; large datasets let a persistent fit advantage accumulate.

If $L(h)$ depends on parameter precision, model cost may itself grow with sample size because more data can justify transmitting weights more accurately. One then optimizes jointly over model and quantization precision.

MAP selects one model by minimizing $-\log p_h(D)-\log\pi(h)$ . A Bayesian mixture code uses $-\log\sum_h\pi(h)p_h(D)$ and need not announce a single hypothesis first. The two protocols can therefore assign different lengths and make different selections.

Exercise 5. NCD by hand

Suppose a compressor gives

C(x)=1000, \qquad C(y)=900, \qquad C(xy)=1300

bytes.

Compute $\operatorname{NCD}_C(x,y)$ .
How does the result change if $C(yx)=1260$ and the minimum is used for symmetrization?
Why is the result not an exact NID?
Name two possible artifacts for short files.

Show answer and solution

Without symmetrization,

\operatorname{NCD}_C(x,y) = \frac{1300-\min(1000,900)}{\max(1000,900)} = \frac{400}{1000} = \boxed{0.40}.

If

C_{\mathrm{sym}}(x,y) = \min\{C(xy),C(yx)\} = 1260,

then

\operatorname{NCD}_{C,\mathrm{sym}}(x,y) = \frac{1260-900}{1000} = \boxed{0.36}.

This is not exact NID because $C$ is not $K$ , the compressor detects only a restricted family of regularities, real files include headers and checksums, ideal normal-compressor properties may fail, and concatenation order can affect dictionary state.

For short files, fixed headers, insufficient data for dictionary learning, block alignment, and irrelevant metadata may dominate.

Compressor suitability should be checked empirically: compare several codecs, both concatenation orders, sensitivity to representation and preprocessing, and held-out nearest-neighbor or clustering performance.

Exercise 6. Python: compressors, prequential MDL, and NCD

Run M10_algorithmic_mdl_experiments.py.

It performs three experiments:

compares gzip, bz2, and LZMA on regular and pseudorandom objects;
compares the prequential length of two representations with similar final accuracy;
builds an NCD matrix for related texts, code fragments, and DNA-like sequences.

Answer the following:

Why do PRNG and SHA streams compress poorly with ordinary compressors despite having short generative descriptions?
Why does the representation with fewer nuisance dimensions obtain a shorter prequential code?
Why does NCD group within-domain pairs while its absolute values depend on bz2?
What checks are required before using NCD as an operational metric?

Show answer and solution

The script uses fixed seeds and settings, so the results are reproducible.

1. Practical compressors

Bits per input byte:

Object	gzip	bz2	LZMA
Zeros	0.0117	0.0052	0.0171
Periodic string	0.0168	0.0078	0.0181
Repeated English-like text	0.0343	0.0216	0.0244
PRNG, seed=7	8.0046	8.0789	8.0078
SHA-256 counter stream	8.0046	8.0756	8.0078

The first three objects contain regularities aligned with compressor inductive biases. The last two have short generative programs but appear statistically random to these algorithms. Format overhead even pushes the archives slightly above the raw eight bits per byte.

2. Prequential MDL

Representation	bits/label	final accuracy
4 informative dimensions	0.7423	0.7440
4 signal + 96 nuisance dimensions	0.9086	0.7270

The second representation contains the same basic signal plus many nuisance dimensions. The probe is less sample-efficient and assigns worse probabilities in early blocks. Prequential coding accumulates this learning cost, while a single final accuracy partly hides it. Even if the final accuracies were exactly equal, the prequential lengths could differ because they depend on the entire learning trajectory.

3. NCD

The smallest off-diagonal distances are the within-domain pairs:

text-A / text-B: about $0.642$ ;
code-A / code-B: about $0.576$ ;
dna-A / dna-B: about $0.601$ .

Most cross-domain distances lie between roughly $0.75$ and $0.99$ .

The diagonal is not exactly zero because headers matter and $C(xx)$ need not equal $C(x)$ . This illustrates the gap between theoretical NID and practical NCD.

Before production use, check robustness across compressors, both concatenation orders, file-size and header effects, preprocessing, held-out clustering or nearest-neighbor performance, and permutation or domain-matched negative baselines.

Code solution · the same source file for RU/EN

PythonM10_algorithmic_mdl_experiments.pyDownload .py

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285

from __future__ import annotations

import bz2
import gzip
import hashlib
import json
import lzma
import math
import random
import zlib
from dataclasses import dataclass
from pathlib import Path
from typing import Callable

import matplotlib
matplotlib.use("Agg")
import matplotlib.pyplot as plt
import numpy as np
from sklearn.linear_model import LogisticRegression
from sklearn.metrics import accuracy_score, log_loss
from sklearn.preprocessing import StandardScaler
from sklearn.pipeline import make_pipeline

ROOT = Path(__file__).resolve().parent
OUT = ROOT / "generated_experiment"
OUT.mkdir(exist_ok=True)

SEED = 20260713
rng = np.random.default_rng(SEED)


def repeat_to_length(pattern: bytes, n: int) -> bytes:
    return (pattern * (n // len(pattern) + 1))[:n]


def python_prng_bytes(n: int, seed: int = 7) -> bytes:
    # A short generator plus a short seed describes this object, even though
    # generic compressors will usually see random-looking bytes.
    r = random.Random(seed)
    return bytes(r.randrange(256) for _ in range(n))


def hash_counter_stream(n: int, seed: bytes = b"course-m10") -> bytes:
    out = bytearray()
    counter = 0
    while len(out) < n:
        out.extend(hashlib.sha256(seed + counter.to_bytes(8, "big")).digest())
        counter += 1
    return bytes(out[:n])


COMPRESSORS: dict[str, Callable[[bytes], bytes]] = {
    "gzip": lambda x: gzip.compress(x, compresslevel=9),
    "bz2": lambda x: bz2.compress(x, compresslevel=9),
    "lzma": lambda x: lzma.compress(x, preset=9),
}


def compressor_experiment(n: int = 65536) -> list[dict[str, float | str]]:
    corpus = {
        "zeros": b"\x00" * n,
        "periodic": repeat_to_length(b"abc123|", n),
        "English-like": repeat_to_length(
            b"prediction and compression are two views of the same log-loss; ", n
        ),
        "PRNG seed=7": python_prng_bytes(n, 7),
        "SHA256 stream": hash_counter_stream(n),
    }

    rows: list[dict[str, float | str]] = []
    for name, data in corpus.items():
        for comp_name, comp in COMPRESSORS.items():
            packed = comp(data)
            rows.append(
                {
                    "object": name,
                    "compressor": comp_name,
                    "raw_bytes": len(data),
                    "compressed_bytes": len(packed),
                    "bits_per_byte": 8.0 * len(packed) / len(data),
                }
            )

    names = list(corpus)
    x = np.arange(len(names))
    width = 0.24
    fig, ax = plt.subplots(figsize=(10.5, 5.6))
    for j, comp_name in enumerate(COMPRESSORS):
        vals = [
            next(
                float(row["bits_per_byte"])
                for row in rows
                if row["object"] == name and row["compressor"] == comp_name
            )
            for name in names
        ]
        ax.bar(x + (j - 1) * width, vals, width=width, label=comp_name)
    ax.axhline(8.0, linewidth=1.2, linestyle="--", label="raw: 8 bits/byte")
    ax.set_xticks(x, names, rotation=18, ha="right")
    ax.set_ylabel("bits per input byte")
    ax.set_title("Practical compressors are computable upper-bound mechanisms, not K-oracles")
    ax.legend(ncol=2)
    fig.tight_layout()
    fig.savefig(OUT / "M10_experiment_compressor_bounds.png", dpi=190)
    plt.close(fig)

    return rows


@dataclass
class PrequentialResult:
    name: str
    total_bits: float
    bits_per_label: float
    final_accuracy: float
    cumulative_points: list[tuple[int, float]]


def make_classification_representations(n: int = 5000) -> tuple[np.ndarray, np.ndarray, np.ndarray]:
    z = rng.normal(size=(n, 4))
    logits = 1.3 * z[:, 0] - 0.9 * z[:, 1] + 0.5 * z[:, 2]
    probs = 1.0 / (1.0 + np.exp(-logits))
    y = rng.binomial(1, probs)

    easy = z + rng.normal(scale=0.08, size=z.shape)
    nuisance = rng.normal(size=(n, 96))
    hard = np.concatenate([z + rng.normal(scale=0.18, size=z.shape), nuisance], axis=1)
    return easy, hard, y.astype(int)


def prequential_code(
    X: np.ndarray,
    y: np.ndarray,
    name: str,
    boundaries: list[int],
) -> PrequentialResult:
    n = len(y)
    if boundaries[-1] != n:
        raise ValueError("last boundary must equal dataset size")

    first = boundaries[0]
    total_bits = float(first)  # uniform binary code for first labels
    points: list[tuple[int, float]] = [(first, total_bits)]

    for left, right in zip(boundaries[:-1], boundaries[1:]):
        model = make_pipeline(
            StandardScaler(),
            LogisticRegression(max_iter=2500, C=1.0, solver="lbfgs", random_state=SEED),
        )
        model.fit(X[:left], y[:left])
        probs = model.predict_proba(X[left:right])
        block_nats = log_loss(y[left:right], probs, labels=[0, 1], normalize=False)
        total_bits += float(block_nats / math.log(2.0))
        points.append((right, total_bits))

    final_model = make_pipeline(
        StandardScaler(),
        LogisticRegression(max_iter=2500, C=1.0, solver="lbfgs", random_state=SEED),
    )
    split = int(0.8 * n)
    final_model.fit(X[:split], y[:split])
    acc = accuracy_score(y[split:], final_model.predict(X[split:]))

    return PrequentialResult(
        name=name,
        total_bits=total_bits,
        bits_per_label=total_bits / n,
        final_accuracy=float(acc),
        cumulative_points=points,
    )


def prequential_experiment() -> list[PrequentialResult]:
    X_easy, X_hard, y = make_classification_representations()
    boundaries = [64, 128, 256, 512, 1024, 2048, 3500, len(y)]
    results = [
        prequential_code(X_easy, y, "4 informative dimensions", boundaries),
        prequential_code(X_hard, y, "4 signal + 96 nuisance dimensions", boundaries),
    ]

    fig, ax = plt.subplots(figsize=(9.6, 5.4))
    for result in results:
        xs = [p[0] for p in result.cumulative_points]
        ys = [p[1] / p[0] for p in result.cumulative_points]
        ax.plot(xs, ys, marker="o", label=result.name)
    ax.axhline(1.0, linestyle="--", linewidth=1.2, label="uniform binary code")
    ax.set_xscale("log", base=2)
    ax.set_xlabel("number of labels encoded")
    ax.set_ylabel("cumulative bits per label")
    ax.set_title("Prequential MDL rewards representations that are learned quickly")
    ax.legend()
    fig.tight_layout()
    fig.savefig(OUT / "M10_experiment_prequential.png", dpi=190)
    plt.close(fig)
    return results


def ncd(x: bytes, y: bytes, compressor: Callable[[bytes], bytes]) -> float:
    cx = len(compressor(x))
    cy = len(compressor(y))
    cxy = min(len(compressor(x + y)), len(compressor(y + x)))
    return (cxy - min(cx, cy)) / max(cx, cy)


def mutate(data: bytes, every: int, replacement: bytes) -> bytes:
    out = bytearray(data)
    for i in range(0, len(out), every):
        out[i : i + len(replacement)] = replacement[: min(len(replacement), len(out) - i)]
    return bytes(out)


def ncd_experiment() -> tuple[list[str], np.ndarray]:
    n = 24000
    objects = {
        "text-A": repeat_to_length(b"the model predicts the next token and pays in bits. ", n),
        "text-B": mutate(repeat_to_length(b"the model predicts the next token and pays in bits. ", n), 337, b"loss"),
        "code-A": repeat_to_length(b"for(i=0;i<n;i++){sum+=a[i];}\n", n),
        "code-B": mutate(repeat_to_length(b"for(i=0;i<n;i++){sum+=a[i];}\n", n), 401, b"while"),
        "dna-A": repeat_to_length(b"ACGTACGTGATTACA", n),
        "dna-B": mutate(repeat_to_length(b"ACGTACGTGATTACA", n), 389, b"TTAA"),
    }
    labels = list(objects)
    comp = lambda b: bz2.compress(b, compresslevel=9)
    matrix = np.zeros((len(labels), len(labels)))
    for i, a in enumerate(labels):
        for j, b in enumerate(labels):
            matrix[i, j] = ncd(objects[a], objects[b], comp)

    fig, ax = plt.subplots(figsize=(7.5, 6.4))
    im = ax.imshow(matrix, vmin=0.0, vmax=max(1.0, float(matrix.max())))
    ax.set_xticks(np.arange(len(labels)), labels, rotation=35, ha="right")
    ax.set_yticks(np.arange(len(labels)), labels)
    ax.set_title("Normalized compression distance: shared regularity becomes proximity")
    for i in range(len(labels)):
        for j in range(len(labels)):
            ax.text(j, i, f"{matrix[i, j]:.2f}", ha="center", va="center", fontsize=8)
    fig.colorbar(im, ax=ax, label="NCD")
    fig.tight_layout()
    fig.savefig(OUT / "M10_experiment_ncd.png", dpi=190)
    plt.close(fig)
    return labels, matrix


def main() -> None:
    compressor_rows = compressor_experiment()
    prequential_results = prequential_experiment()
    labels, matrix = ncd_experiment()

    summary = {
        "compressor_rows": compressor_rows,
        "prequential": [
            {
                "name": r.name,
                "total_bits": r.total_bits,
                "bits_per_label": r.bits_per_label,
                "final_accuracy": r.final_accuracy,
            }
            for r in prequential_results
        ],
        "ncd_labels": labels,
        "ncd_matrix": matrix.tolist(),
    }
    (OUT / "M10_experiment_results.json").write_text(
        json.dumps(summary, indent=2, ensure_ascii=False), encoding="utf-8"
    )

    print("Compression experiment (bits per byte):")
    for row in compressor_rows:
        print(
            f"  {row['object']:14s} {row['compressor']:4s}: "
            f"{float(row['bits_per_byte']):.3f}"
        )
    print("\nPrequential results:")
    for r in prequential_results:
        print(
            f"  {r.name}: {r.bits_per_label:.4f} bits/label, "
            f"final accuracy={r.final_accuracy:.4f}"
        )
    print("\nNCD matrix:")
    print(np.array2string(matrix, precision=3, suppress_small=True))


if __name__ == "__main__":
    main()

Bonus. Universal dominance and excess log loss

Assume the universal semimeasure satisfies

M(x) \ge 2^{-K(\mu)-c}\mu(x)

for every finite prefix $x$ of a computable source $\mu$ .

Show that
$\log_2\frac{\mu(x)}{M(x)} \le K(\mu)+c.$
Decompose the likelihood ratio over time using the chain rule.
Explain why this yields a finite cumulative excess log-loss bill without making the universal predictor computable.

Show answer and solution

From

M(x) \ge 2^{-K(\mu)-c}\mu(x),

we get

\frac{\mu(x)}{M(x)} \le 2^{K(\mu)+c}.

Taking a base-two logarithm,

\boxed{ \log_2\frac{\mu(x)}{M(x)} \le K(\mu)+c }.

For a sequence with well-defined conditionals,

\begin{aligned} \log\frac{\mu(x_{1:n})}{M(x_{1:n})} &= \log \prod_{t=1}^{n} \frac{\mu(x_t\mid x_{<t})}{M(x_t\mid x_{<t})}\\ &= \sum_{t=1}^{n} \log \frac{\mu(x_t\mid x_{<t})}{M(x_t\mid x_{<t})}. \end{aligned}

Taking expectation under $\mu$ turns each term into a conditional KL divergence. Thus cumulative expected excess log loss is bounded by $K(\mu)+O(1)$ bits. The true model's complexity is paid through the factor $2^{-K(\mu)}$ , which becomes the additive term $K(\mu)$ after taking logarithms.

The bound does not make $M$ computable. The semimeasure is lower semicomputable: discovering additional programs can increase partial sums, but no algorithm can know that no unseen program will contribute later. Conditional ratios do not become a computable oracle either.