Optimal finite state universal coding of individual sequences
Eado Meron, Meir Feder · 2004
The problem of assigning a probability to the next outcome of an individual binary sequence under the constraint that the universal predictor has a finite number of states, is explored. The two main loss functions that are considered are the square error loss and the self-information loss. Universal prediction w.r.t. the self-information loss can be combined with arithmetic encoding to construct a universal encoder, thus explores the universal coding problem. The performance of randomized time-invariant K-state universal predictors, and provide performance bounds in terms of the number of states K for long enough sequences is analyzed. In the case where the comparison class consists of constant predictors for the square error loss, the tight bounds indicating that the optimal asymptotic expected redundancy is O(1/K) is provided. An upper bound on the coding redundancy of O((log K)/K) and a lower bound of O(1/K) is shown for the self-information loss.