Stochastic complexity and universal modeling

Abstract

The idea of a universal code, due to Kolmogorov, is to design a code for a parametric family of sources, or random processes, which reaches the entropy as the limiting mean per symbol length no matter which member in the family generates the indefinitely growing data string. It is a testimony to the fundamental property of the code length that, if we do not settle merely for reaching the per symbol entropy as the limit but strive for the shortest code length for each long sequence, the code length actually defines a universal process as a model which imitates the behavior of any process or model in the family, much as a universal Turing machine imitates any special purpose machine. The shortest code length of a string, which we call its stochastic complexity, relative to the given family of processes, turns out to extend Shannon's information in the sequence in a manner that submits the entire field of statistics as just a branch in information theory - albeit a singularly important one.