It is well known in the theory of Kolmogorov complexity that most strings cannot be compressed; more precisely, only exponentially few (Theta(2(n-m))) binary strings of length n can be compressed by m bits. This paper extends the 'incompressibility' property of Kolmogorov complexity to the 'unpredictability' property of predictive complexity. The 'unpredictability' property states that predictive complexity (defined as the loss suffered by a universal prediction algorithm working infinitely long) of most strings is close to a trivial upper bound (the loss suffered by a trivial minimax constant prediction strategy). We show that only exponentially few strings can be successfully predicted and find the base of the exponent. (c) 2005 Elsevier Inc. All rights reserved.
展开▼
