OPTIMAL SEQUENTIAL PROBABILITY ASSIGNMENT FOR INDIVIDUAL SEQUENCES

The problem of sequential probability assignment for individual sequen ces is investigated. We compare the probabilities assigned by any sequ ential scheme to the performance of the best ''batch'' scheme (model) in some class. For the class of finite-state schemes and other related families, we derive a deterministic performance bound, analogous to t he classical (probabilistic) Minimum Description Length (MDL) bound. I t holds for ''most'' sequences, similarly to the probabilistic setting , where the bound holds for ''most'' sources in a class. It is shown t hat the bound can be attained both pointwise and sequentially for any model family in the reference class and without any prior knowledge of its order. This is achieved by a universal scheme based on a mixing a pproach. The bound and its sequential achievability establish a comple tely deterministic significance to the concept of predictive MDL.