Kolmogorov Complexity and the Two-Part MDL Code

Shannon entropy answers a question about an ensemble: how many bits does a symbol from this distribution cost on average. It gives the same answer for two files of equal length drawn from the same source, even if one is a run of zeros and the other is a table of random bytes. That answer is correct for the ensemble and useless for the individual file, and the gap between the two questions is where algorithmic information theory begins. What Shannon Entropy as the Expected Cost of an Outcome defines over an ensemble, complexity defines for a single object.

The definition, and why it cannot be computed

Fix a universal Turing machine $U$. The Kolmogorov complexity of a string $x$ is the length of the shortest program $p$ such that $U(p)$ outputs $x$ and halts:

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

The choice of $U$ changes $K$ by at most an additive constant: a program for one machine can be simulated by another with a fixed interpreter prefix, and the prefix’s length does not depend on $x$. This invariance is what makes the definition objective, and the constant is the price of the objectivity: for short strings it can exceed the complexity itself, so $K$ is only meaningful up to an additive constant that depends on the machine.

$K$ is not computable. If it were, one could write a program that enumerates strings in order of increasing length, computes $K$ for each, and outputs the first string whose complexity exceeds the length of this program. That string would then be specified by a program shorter than its own complexity, a contradiction. The argument is Berry’s paradox in computational form, and it is the reason no compressor can be optimal in the sense of achieving $K$.

$K$ is not the same as compressed size. A program that builds a decompressor and appends the compressed bytes is an achievable description, so a compressor’s output gives an upper bound on $K$: if a string compresses to $m$ bits, its complexity is at most $m$ plus the length of the decompressor, which is a constant for a fixed algorithm. The bound is one-sided, and for some inputs the gap between it and $K$ is arbitrarily large because the compressor’s model does not fit; no single algorithm closes that gap uniformly.

Incompressibility, and why most strings are random

A counting argument gives the central fact. There are $2^n$ binary strings of length $n$ but fewer than $2^{n-k}$ programs of length below $n-k$, so at most that many strings of length $n$ can have complexity below $n-k$; the remaining fraction, $1 - 2^{-k}$, therefore satisfies $K(x) \ge n - k$. Strings compressible by more than $k$ bits are exponentially rare in $k$.

This is why a general-purpose compressor cannot compress arbitrary data and why it must expand incompressible input slightly. Every compressor has an output alphabet and a framing overhead, so on random input the output is a few percent larger. The correct response is a stored-block escape, not a better algorithm.

The incompressibility fact has a second use: it certifies randomness in a way that statistical tests cannot. A string that passes every statistical test for randomness can still be highly compressible: a pseudorandom generator’s output passes tests designed without knowledge of the generator, while its complexity is bounded by the seed length. $K$ is the right notion, and it is uncomputable, so the practical substitute is a battery of compressors used as upper bounds: if a string compresses under several independent algorithms, it is not random, whatever the tests say.

Two-part codes and the MDL principle

The uncomputable definition becomes usable when it is restricted to a model class. Choose a family of probability models $\mathcal{M}$, each with a description length $L(\theta)$ for its parameters, and encode data $x$ under model $\theta$ with length $-\log_2 p(x \mid \theta)$. The total description is

$$L(x) = L(\theta) + \left(-\log_2 p(x \mid \theta)\right) + O(1)$$

and the model minimizing this total is the one selected. The first term is the cost of stating the model; the second is the cost of the data given the model. Adding parameters reduces the second term and increases the first, and the minimum trades them off.

The trade-off is exactly the bias-variance trade in statistical estimation, expressed in bits. A model with too few parameters cannot describe the data and pays in the second term. A model with too many parameters describes the training data precisely and pays in the first term, and the total exceeds the simpler model’s when the extra parameters are fitting noise rather than structure.

For a model with $k$ real-valued parameters estimated from $n$ observations, a mixture code with a smooth prior over the parameters produces a parameter cost of about $\tfrac{k}{2}\log_2 n$ bits. The derivation is geometric: the region of parameter space that the data cannot distinguish from the maximum-likelihood estimate shrinks like $n^{-k/2}$ in volume as $n$ grows, and describing a point in a shrinking region costs the logarithm of that volume. The Akaike criterion instead charges a flat penalty of one nat per parameter, which is the price of describing a parameter to a fixed precision rather than letting the precision improve with the data; the two penalties agree on the order but not on the constant, and the BIC penalty, which is $\tfrac{k}{2}\ln n$ nats, coincides with the mixture cost rather than with the AIC one. The disagreement is visible only when the likelihoods of the competing models differ by a few bits.

A universal code over a countable model class makes the same idea exact without a parameter count. The mixture code assigns $p(x) = \sum_{\theta} w(\theta) p(x \mid \theta)$, and its length is bounded by the best single model’s length plus $-\log_2 w(\theta^*)$, the cost of identifying the best model. Choosing weights that decay fast enough makes the identification cost grow only logarithmically in the number of models considered, which is why the mixture formulation is the cleaner theoretical object.

Where the criterion misleads

The two-part code is a valid criterion under specific conditions, and the conditions are routinely violated.

The model class must contain the truth. If no model in $\mathcal{M}$ generates the data, the selection is a statement about approximation rather than about the generating process, and the code length of the selected model measures its divergence from the data rather than the data’s true information content. This is not a defect of MDL; it is a defect of the assumption.

The data must be exchangeable or stationary. The code length is computed as if the data were a sequence from a fixed model. For data with drift, the total code length conflates the model’s misfit with the drift, and a model that adapts is penalized for its adaptation cost even when adaptation is correct. Block-wise or adaptive variants handle this by allowing the model to change, at the cost of a per-block description.

The description must be decodable. Any model can be described in zero bits if the decoder is allowed to know it in advance. The comparison is only meaningful when the same decoder is used for all models, and the decoder’s own complexity is the additive constant that the asymptotic analysis discards. In a comparison between two models whose description lengths differ by a few bits, that constant can decide the outcome.

Likelihood is not the objective. Minimizing description length minimizes expected code length under the model, which is the wrong objective when the downstream cost of an error is asymmetric. A model selected by MDL is a good compressor, not necessarily a good predictor, and the two diverge whenever the loss function is not log loss.

import math

data = 'abracadabra'
n = len(data)
counts = {c: data.count(c) for c in set(data)}

# data term: the negative log-likelihood in bits under the empirical model
data_bits = -sum(c * math.log2(c / n) for c in counts.values())

def model_bits(k):
    # k parameters, each charged (1/2) * log2(n) bits (the BIC-shaped term)
    return 0.5 * k * math.log2(n)

for k in (1, 2, 8):
    print(k, round(model_bits(k) + data_bits, 3))

The data term is fixed once the symbols are counted, so the printed total is increasing in $k$ for this input: the extra parameters of a richer model never earn their description back unless they change the predicted probabilities. That is the whole content of the two-part criterion, and the code shows it rather than asserting it.

Compressibility, structure, and the limits of the analogy

It is tempting to treat $K(x)$ as the true information content of $x$ and the entropy as an approximation. The relationship is a pair of inequalities rather than an equality. For a string drawn from a computable distribution $P$, $K(x)$ is at most $-\log_2 P(x)$ plus a constant, since a program can encode the distribution and then the symbols. In the other direction the bound is statistical rather than pointwise, and it does not follow from counting programs: an unseen symbol can have high $K$ at any length. The applicable statement is the entropy lower bound, which says that for each $k$ the probability that the ideal code length of the first $n$ symbols of the source is less than the source entropy by more than $k$ bits is at most $2^{-k}$. So entropy and complexity agree for typical strings from a computable source, and diverge for atypical ones. The all-zeros string of length $n$ has self-information $n$ under the uniform distribution and complexity $O(\log n)$, because a program of roughly $\log_2 n$ bits can carry $n$ as a counter and print zeros; both statements are correct about different things.

The divergence is the reason the two notions serve different purposes. Entropy is the right tool for designing a code for an ensemble, which is what a compressor does when it estimates a distribution from data. Complexity is the right tool for asking whether a particular object has structure, which is what a randomness test or a model-selection criterion is doing. Confusing them produces claims like “this file has entropy 3.2 bits per byte” when what is meant is “this compressor’s model assigns an average of 3.2 bits per byte,” and the second claim is the one that can be checked.

The practical residue of the theory is a discipline rather than an algorithm. Every description has two parts, model and data; every model choice has a cost that must be paid; and the cost is measured in the same units as the savings. That accounting is what distinguishes a model that generalizes from one that memorizes, and it is the same accounting that Entropy Rate of a Markov Source and the Value of Context performs when it charges a context model for the contexts it creates.