ECCC-Report TR01-052https://eccc.weizmann.ac.il/report/2001/052Comments and Revisions published for TR01-052en-usMon, 16 Jul 2001 18:21:09 +0300
Paper TR01-052
| Non-linear Inequalities between Predictive and Kolmogorov Complexity |
Mikhail V. Vyugin,
Vladimir Vyugin
https://eccc.weizmann.ac.il/report/2001/052Predictive 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.
Mon, 16 Jul 2001 18:21:09 +0300https://eccc.weizmann.ac.il/report/2001/052