Stochastic Complexity

Abstract

SUMMARY It is argued that all the useful information in observed data that can be extracted with a selected class of modeled distributions, will be obtained if we calculate the stochastic complexity, defined to be the shortest description length of the data. The same quantity also determines the greatest lower bound for prediction errors when the data are sequentially predicted. An abstract definition of stochastic complexity is given along with two fundamental theorems which justify the notion. Further, three explicit model selection criteria to approximate the stochastic complexity are described and the associated optimal models are interpreted to define asymptotically sufficient statistics for the data.