Non-linear Inequalities between Predictive and Kolmogorov Complexities

Authors: Michael V. Vyugin and Vladimir V. V'yugin.

Source: Lecture Notes in Artificial Intelligence Vol. 2225, 2001, 190 - 204.

Abstract. Predictive complexity is a generalization of Kolmogorov complexity. It corresponds to an "optimal" prediction strategy which gives a lower bound to ability of any algorithm to predict elements of a sequence of outcomes. A variety of types of loss functions makes it interesting to study relations between corresponding predictive complexities.

Non-linear inequalities (with variable coefficients) between predictive complexity $KG(x)$ of non-logarithmic type and Kolmogorov complexity $K(x)$ (which is close to predictive complexity for logarithmic loss function) are the main subject of consideration in this paper. We deduce from these inequalities an asymptotic relation $\sup\limits_{x:l(x)=n}\frac{K(x)}{KG(x)}\sim\frac{1}{a}\log n$, when $n\to\infty$, where a is a constant and $l(x)$ is the length of a sequence $x$. An analogous asymptotic result holds for relative complexities $K(x)/l(x)$ and $KG(x)/l(x)$. To obtain these inequalities we present estimates of the cardinality of all sequences of given predictive complexity.

©Copyright 2001 Springer