Skip to search boxSkip to navigationSkip to main content

On-line probability, complexity and randomness

  • Alexey Chernov
    ,
  • Alexander Shen
    ,
  • Nikolai Vereshchagin
    ,
  • Vladimir Vovk
Research Output: Chapter in Book/Report/Conference proceeding Conference contribution Peer-review

Abstract

Classical probability theory considers probability distributions that assign probabilities to all events (at least in the finite case). However, there are natural situations where only part of the process is controlled by some probability distribution while for the other part we know only the set of possibilities without any probabilities assigned. We adapt the notions of algorithmic information theory (complexity, algorithmic randomness, martingales, a priori probability) to this framework and show that many classical results are still valid.

Publication Information

Output type

Research Output: Chapter in Book/Report/Conference proceeding Conference contribution Peer-review

Original language

English

Pages from-to (Number of pages)

Pages 138–153

Publication milestones

  • Published - 01/01/2008

Publication status

Published - 01/01/2008

Publisher

Springer, Japan, India, Australia, Germany, United States, United Arab Emirates, Austria, Switzerland, Italy, China, United Kingdom, Netherlands, Brazil, France, Singapore

ISBN (Print)

9783540879862

ISBN (Electronic)

9783540879862

External Publication IDs

  • handle.net: 10547/279181
  • Scopus: 56749103109

Host publication title

Algorithmic Learning Theory

Access to documents

Publication metrics