Predicting the “Unpredictable”

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 information about 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 these cases 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 methods that guarantee a small error no matter what process generates the sequence?