Predictive stochastic complexity and model estimation for finite-state processes

Abstract

It is shown that the predictive and nonpredictive stochastic complexities relative to the class of finite-state models are asymptotically equivalent in a probabilistic sense. To this end, a universal, sequential, noiseless coding scheme attaining the minimum description length (MDL) of the data with respect to this class is presented and investigated. It relies on an MDL-based estimator of the model structure, which is proved to be strongly consistent. An interpretation of this result is that a process 'close' to every process in the class, regardless of the model structure, can be constructed. This universal process can be employed in the solution of sequential decision problems like coding, prediction, and gambling, in an asymptotically optimal manner. © 1994.