SOME PROPERTIES OF SEQUENTIAL PREDICTORS FOR BINARY MARKOV SOURCES

Universal prediction of the next outcome of a binary sequence drawn fr om a Markov source with unknown parameters is considered. For a given source, the predictability is defined as the least attainable expected fraction of prediction errors. A lower bound is derived on the maximu m rate at which the predictability is asymptotically approached unifor mly over all sources in the Markov class. This bound is achieved by a simple majority predictor. For Bernoulli sources, bounds on the large deviations performance are investigated. A lower bound is derived for the probability that the fraction of errors will exceed the predictabi lity by a prescribed amount DELTA > 0. This bound is achieved by the s ame predictor if DELTA is sufficiently small.