Stochastic complexity

Stochastic complexity is the generalization of the minimum description length principle to non-parametric and infinite model classes. Rather than comparing fixed parameter spaces, stochastic complexity measures the minimum number of bits required to encode a sequence using the best model from a nested sequence of model classes. It was developed by Jorma Rissanen as a way to make MDL applicable to problems where the number of parameters is not fixed in advance. Stochastic complexity connects MDL to universal coding and the theory of algorithmic information.

Stochastic Complexity and Universal Coding

Stochastic complexity generalizes the Minimum description length principle by asking not merely 'what is the shortest description of this data?' but 'what is the shortest description using the best model from a nested hierarchy of model classes?' This nesting is crucial. It allows the theory to compare a one-parameter model against a two-parameter model, a polynomial against a neural network, without committing to a fixed dimensional space. The complexity of a data sequence is the length of the shortest code that can be constructed for it using the optimal model from the optimal class.

This connects stochastic complexity to universal coding and to the theory of algorithmic information. Where Kolmogorov complexity asks for the shortest program that outputs a sequence, stochastic complexity asks for the shortest program that outputs a sequence while being learnable from a parameterized family. The difference is not merely technical: Kolmogorov complexity is uncomputable, while stochastic complexity is computable for well-defined model classes. It is the practical shadow of an ideal cast on the world of statistical inference.

Stochastic Complexity as a Systems Property

Stochastic complexity is not merely a statistical measure. It is a systems property: it characterizes the complexity of a phenomenon relative to the representational resources available to describe it. A sequence that is complex under one model class may be simple under another. Complexity is not in the data alone; it is in the relationship between data and description.

This relational character makes stochastic complexity relevant to Informational collapse and the theory of epistemic architecture. A system that uses an impoverished model class will assign high stochastic complexity to phenomena that another system, with a richer model class, finds simple. The complexity is not a property of the world but of the world's coupling with a representational system. This is why technological solutions to complex problems often fail: they do not change the model class, they merely add data to a framework that cannot absorb it.

The measure also illuminates the trade-off between model flexibility and model reliability. A model class that is too rich will fit noise; one that is too poor will miss signal. Stochastic complexity captures this trade-off not as a parameter to be tuned but as an intrinsic property of the modeling relationship itself.

The claim that stochastic complexity provides an objective measure of data complexity is a category error. There is no complexity without a model class, and no model class without a modeler. Stochastic complexity is not a property of the world; it is a property of the dialogue between a mind and its data. Any theory that treats it as ontological is not doing statistics — it is doing metaphysics badly.