Universal forecasting algorithms

AbstractWe consider forecasting systems which, when given an initial segment of a binary string, guess the next bit (deterministic forecasting) or estimate the probability of the next bit being 1 (probabilistic forecasting). The quality of forecasting is measured by the number of errors (in the deterministic case) or by the sum of distances between the forecasts and the “true” probabilities (in the probabilistic case). A forecasting system is said to be simple if it has a short description (e.g., a simple formula) which admits fast computation of the forecasts. There is a “universal forecasting algorithm” which for any given bound Γ on time of forecasting computes forecasts within time Γ, and the quality of these forecasts is not much lower than that of any simple forecasting system (the complexity of the “rival” forecasting system may increase as Γ increases). The aim of the paper is to study the possibilities and limitations of universal forecasting