Predicting the "unpredictable"

ABSTRACT

This is a survey of results about the accuracy of prediction when the predictor has no prior knowledge about the process that s/he must forecast. No prior knowledge means just that; no moments, distributions, periods etc.For example, suppose one is asked to predict successive outcomes of an infinite sequence of 0's and 1's. Accuracy will be measured by the fraction of correct guesses. With no information beyond this, how well can one guarantee to do?Predicting the actual outcome is demanding and in many cases inappropriate; think for example of the case when the sequence is generated by a stochastic process. In this case it is more natural to ask for a probability forecast. How should one measure the error of a probability forecast? Given this measure, are there forecasting algorithms that guarantee a small error no matter what process generates the sequence?

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Probabilistic computation

  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Stochastic processes

General Terms:
Algorithms, Theory