TR01-052 Authors: Mikhail V. Vyugin, Vladimir Vyugin

Publication: 16th July 2001 18:21

Downloads: 1195

Keywords:

Predictive complexity is a generalization of Kolmogorov complexity

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 between predictive complexity of non-logarithmic

type and Kolmogorov complexity (which is close to predictive complexity

for logarithmic loss function) are the main subject of consideration

in this paper. We prove that asymptotically they differ on sequences

of length $n$ in the worst case by a factor equal to $\log n$. These estimates

cannot be improved. To obtain these inequalities we present estimates

of the cardinality of all sequences of given predictive complexity.