Predictive Complexity for Games with Finite Outcome Spaces

Research output: Chapter in Book/Report/Conference proceedingChapter

1004 Downloads (Pure)

Abstract

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
PublisherSpringer
Chapter8
Pages117-139
Number of pages23
ISBN (Electronic)978-3-319-21852-6
ISBN (Print)978-3-319-21851-9
DOIs
Publication statusE-pub ahead of print - 4 Sep 2015

Cite this