Predictive Complexity for Games with Finite Outcome Spaces

Research output: Chapter in Book/Report/Conference proceedingChapter

1079 Downloads (Pure)


Predictive complexity is a generalization of Kolmogorov complexity motivated by an on-line prediction scenario. It quantifies the “unpredictability” of a sequence in a particular prediction environment. This chapter surveys key results on predictive complexity for games with finitely many outcomes. The issues of existence, non-existence, uniqueness, and linear inequalities are covered.
Original languageEnglish
Title of host publicationMeasures of Complexity
Subtitle of host publicationFestschrift for Alexey Chervonenkis
EditorsVladimir Vovk, Harris Papadopoulos, Alexander Gammerman
Number of pages23
ISBN (Electronic)978-3-319-21852-6
ISBN (Print)978-3-319-21851-9
Publication statusE-pub ahead of print - 4 Sept 2015

Cite this