On complexity of easy predictable sequences

Michael V. Vyugin, Vladimir V. V'yugin

Research output: Contribution to journalArticlepeer-review

2 Citations (Scopus)

Abstract

Predictive complexity is a generalization of Kolmogorov complexity. It corresponds to an "optimal" prediction strategy and gives a natural lower bound to ability of any algorithm to predict elements of a sequence of outcomes. A natural question is studied: how complex can easy-to-predict sequences be? The standard measure of complexity, used in the paper, is Kolmogorov complexity K (which is close to predictive complexity for logarithmic loss function). The difficulty of prediction is measured by the notion of predictive complexity KG for bounded loss function (of nonlogarithmic type). We present an asymptotic relation supx:/(x)=n K(x\n)/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 relation holds for relative complexities K(x | n)/n and KG(x)/n, where n=l(x). To obtain these results we present lower and upper bounds of the cardinality of all sequences of given predictive complexity.

Original languageEnglish
Pages (from-to)241-252
Number of pages12
JournalInformation and Computation
Volume178
Issue number1
DOIs
Publication statusPublished - 10 Oct 2002
Externally publishedYes

Fingerprint

Dive into the research topics of 'On complexity of easy predictable sequences'. Together they form a unique fingerprint.

Cite this