Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR01-043 | 26th April 2001 00:00

Predictive complexity and information


Authors: Mikhail V. Vyugin, Vladimir Vyugin
Publication: 18th June 2001 15:38
Downloads: 1878


A new notion of predictive complexity and corresponding amount of
information are considered.
Predictive complexity is a generalization of Kolmogorov complexity
which bounds the ability of any algorithm to predict elements of
a sequence of outcomes. We consider predictive complexity for a wide class
of bounded loss functions which are generalization of square-loss function.
Relations between unconditional $KG(x)$ and conditional $KG(x|y)$
predictive complexities are studied. We define an algorithm
which has some ``expanding property''. It transforms with positive
probability sequences of given predictive
complexity into sequences of essentially bigger predictive complexity.
A concept of amount of predictive information $IG(y:x)$ is studied. We show
that this information is non-commutative in a very strong sense and present
asymptotic relations between values $IG(y:x)$, $IG(x:y)$, $KG(x)$ and

ISSN 1433-8092 | Imprint