On Complexity of Easy Predictable Sequences

AbstractPredictive complexity is a generalization of Kolmogorov complexity. It corresponds to an “optimal” prediction strategy and gives a natural lower bound to ability of any algorithm to predict elements of a sequence of outcomes. A natural question is studied: how complex can easy-to-predict sequences be? The standard measure of complexity, used in the paper, is Kolmogorov complexity K (which is close to predictive complexity for logarithmic loss function). The difficulty of prediction is measured by the notion of predictive complexity KG for bounded loss function (of nonlogarithmic type). We present an asymptotic relation supx:l(x)=nK(x|n)KG(x)∼1alog n, when n→∞, where a is a constant and l(x) is the length of a sequence x. An analogous asymptotic relation holds for relative complexities K(x|n)/n and KG(x)/n, where n=l(x). To obtain these results we present lower and upper bounds of the cardinality of all sequences of given predictive complexity