Non-linear Inequalities between Predictive and Kolmogorov Complexities

摘要

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_(x:l(x)=n) [K(x)/KG(x)] ～ [1/a] log n, when n → ∞ , 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.