Universal prediction of individual sequences

The problem of sequentially determining the next, future, outcome of a specific binary individual sequence, based on its observed past, using a finite state predictor is considered. The authors define the finite state predictability of the (infinite) sequence x₁ . . . z_n . . . as the minimum fraction of prediction errors that can be made by any such predictor, and prove that this can be achieved, upto an arbitrary small prescribed distance, for each individual sequence, by fully sequential guessing schemes. The rate at which the sequential guessing schemes approach the predictability is calculated. An efficient guessing procedure is based on the incremental parsing algorithm used in Lempel-Ziv data compression, and its fraction of errors also approaches the predictability of the sequence. Some relations between compressibility and predictability are discussed and use of the predictability as an additional measure for the complexity, or randomness, of the sequence is suggested