About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
ISIT 1994
Conference paper
Optimal sequential probability assignment for individual sequences
Abstract
We compare the probabilities assigned to individual sequences by any sequential scheme, with the performance of the best 'batch' scheme in some class. For the class of finite-state (FS0 schemes and other related families, we derive a deterministic performance bound, analogous to the classical (probabilistic) Minimum Description Length (MDL) bound. It holds for 'most' sequences, similarly to the probabilistic setting where the bound holds for 'most' sources in a class. It is shown that 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. The bound and its sequential achievability establish a completely deterministic significance to the concept of predictive MDL.