SEECS Colloquium

A predictor is a deterministic program which from the input of a sequence of symbols of length n provides the most likely value of the (n+1)th symbol that follows. Of course the random generator of the sequence (memoriless, Markov, mixing) is unknown. We present a predictor based on pattern matching which has the property to be optimal on a large class of sequence generators. Predictors have numerous applications (computers, networking, etc).