Large Systems

Algorithmic Approach to the Prediction Problem

B. Ya. Ryabko


Abstract: 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.

UDC: 621.391.1:681.3

Received: 13.05.1992

 English version: Problems of Information Transmission, 1993, 29:2, 186–193

Bibliographic databases:

• 
•