Universal prediction of individual binary sequences in the presence of noise

The problem of predicting the next outcome of an individual binary sequence , based on noisy observations of the past, is considered. The goal of the p redictor is to perform, for each individual sequence, "almost" as well as t he best in a set of experts, where performance is evaluated using a general loss function. A comprehensive approach to prediction in this noisy settin g is presented and proven generally efficient under appropriate conditions. As an illustration of the applicability of the approach suggested for conc rete situations, two important special cases are explicitly treated. The fi rst is the case where the data-corrupting noise process is binary-valued (w here the observed bit is the bitwise XOR of the clean bit and the noise bit ). The second case is that of real-valued additive noise. It is shown that even in this more challenging situation, where the information available to the predictor regarding the past sequence is incomplete, a predictor can b e guaranteed to successfully compete with a whole set of experts in conside rably strong senses.