  Algorithmic theories of randomness can be related to theories of
probabilistic sequence prediction through the notion of a predictor, defined as
a function which supplies lower bounds on initial-segment probabilities of
infinite sequences. An infinite binary sequence $z$ is called unpredictable iff
its initial-segment "redundancy" $n+\log p(z(n))$ remains sufficiently low
relative to every effective predictor $p$. A predictor which maximizes the
initial-segment redundancy of a sequence is called optimal for that sequence.
It turns out that a sequence is random iff it is unpredictable. More generally,
a sequence is random relative to an arbitrary computable distribution iff the
distribution is itself an optimal predictor for the sequence. Here "random" can
be taken in the sense of Martin-L\"{o}f by using weak criteria of
effectiveness, or in the sense of Schnorr by using stronger criteria of
effectiveness. Under the weaker criteria of effectiveness it is possible to
construct a universal predictor which is optimal for all infinite sequences.
This predictor assigns nonvanishing limit probabilities precisely to the
recursive sequences. Under the stronger criteria of effectiveness it is
possible to establish a law of large numbers for sequences random relative to a
computable distribution, which may be useful as a criterion of "rationality"
for methods of probabilistic prediction. A remarkable feature of effective
predictors is the fact that they are expressible in the special form first
proposed by Solomonoff. In this form sequence prediction reduces to assigning
high probabilities to initial segments with short and/or numerous encodings.
This fact provides the link between theories of randomness and Solomonoff's
theory of prediction.
