Algorithmic Approach to the Prediction Problem

A problem on prediction of the elements of an arbitrary sequence x$x_1,x_2,x_3,\dots,$ is considered; the element $x_{t+1}$ is to be predicted from $x_1, x_2\dots x_t$. No assumption is made about the probability structure of the sequence. The game-theoretic approach proposed by J. Kelly is used; the prediction efficiency is estimated by a gain value in a certain game. The relation of the maximal gain value to the Kolmogorov complexity is found. The Hausdorff dimension of the sets of effectively ptimated. An optimal method of prediction is found for the class of finite automata.