Predictive Complexity for Games with Finite Outcome Spaces. / Kalnishkan, Yuri.

Measures of Complexity: Festschrift for Alexey Chervonenkis. ed. / Vladimir Vovk; Harris Papadopoulos; Alex Gammerman. Springer-Verlag, 2015. p. 117-139 8.

Research output: Chapter in Book/Report/Conference proceedingChapter

Published

Documents

  • pc_finite

    Accepted author manuscript, 381 KB, PDF-document

Abstract

Predictive complexity is a generalisation of Kolmogorov complexity motivated by an on-line prediction scenario. It quantifies ``unpredictability'' of a sequence in a particular prediction environment. This paper 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, Alex Gammerman
PublisherSpringer-Verlag
Pages117-139
Number of pages23
ISBN (Electronic)978-3-319-21852-6
ISBN (Print)978-3-319-21851-9
StatePublished - 2015
This open access research output is licenced under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License.

ID: 22650071