Twofold universal prediction schemes for achieving the finite-state predictability of a noisy individual binary sequence

The problem of predicting the next outcome of an individual binary sequence corrupted by noise using finite memory, is considered. The conditional fin ite-state (FS) predictability of an infinite individual sequence given its noisy version is defined as the minimum fraction of errors that can be made by any FS predictor fed by the noisy version. It is proved that the condit ional FS predictability can be attained almost surely by universal sequenti al prediction schemes in the case where the noisy version is the output of a binary-symmetric channel (BSC) whose input is the clean individual sequen ce. In particular, universal predictors of the original noise-free setting, which operate on the noisy sequence, have this property. Moreover, these u niversal predictors do not depend on the crossover probability characterizi ng the BSC, It is seen that the noisy setting gives rise to additional crit eria by which the performance of prediction schemes can be assessed. Finall y, a closer look is taken at the conditional FS predictability, and this qu antity is proposed as an additional measure of the complexity of a sequence , perhaps finer and more informative than the predictive complexity of the noise-free setting.