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.