A simple randomized algorithm for sequential prediction of ergodic time series

We present a simple randomized procedure for the prediction of a binary seq uence. The algorithm uses ideas from recent developments of the theory of t he prediction of individual sequences. We show that if the sequence is a re alization of a stationary and ergodic random process then the average numbe r of mistakes converges, almost surely, to that of the optimum, given hy th e Bayes predictor. The desirable finite-sample properties of the predictor are illustrated hy its performance for Markov processes. In such cases the predictor exhibits near-optimal behavior even without knowing the order of the Markov process. Prediction with side information is also considered.