Prediction and Adaptive Coding of Processes with Large and Infinite Alphabets

The problem of predicting a sequence x, x, … generated by a discrete source with unknown statistics is considered. Each letter x is predicted using the information on the word xx … x only. Such prediction is a classical problem which history can be traced back to Laplace. The problem where the sequence is generated by an i.i.d. source with some large (or even infinite) alphabet, is considered. We suggest and investigated a new class of methods (so called treelike predictors). In particular, a treelike predictor is presented for which the error of prediction goes to 0 even for an infinite alphabet