On-Line Probability, Complexity and Randomness

Alexey Chernov, Alexander Shen, Nikolai Vereshchagin, Vladimir Vovk

Research output: Chapter in Book/Conference proceeding with ISSN or ISBNConference contribution with ISSN or ISBN

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 frame work and show that many classical results are still valid.
Original languageEnglish
Title of host publication19th International Conference, ALT 2008
Place of PublicationBerlin
PublisherSpringer
Pages138-153
Number of pages16
Volume5254
ISBN (Print)9783540879862
DOIs
Publication statusPublished - 31 Dec 2008
Event19th International Conference, ALT 2008 - Budapest, Hungary, October 13-16, 2008
Duration: 31 Dec 2008 → …

Publication series

NameLecture Notes in Computer Science

Conference

Conference19th International Conference, ALT 2008
Period31/12/08 → …

Bibliographical note

© Springer-Verlag Berlin Heidelberg 2008

Fingerprint Dive into the research topics of 'On-Line Probability, Complexity and Randomness'. Together they form a unique fingerprint.

  • Cite this

    Chernov, A., Shen, A., Vereshchagin, N., & Vovk, V. (2008). On-Line Probability, Complexity and Randomness. In 19th International Conference, ALT 2008 (Vol. 5254, pp. 138-153). (Lecture Notes in Computer Science). Springer. https://doi.org/10.1007/978-3-540-87987-9_15