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 ISBNResearchpeer-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 frame work and show that many classical results are still valid.
Original languageEnglish
Title of host publication19th International Conference, ALT 2008
Place of PublicationBerlin
Pages138-153
Number of pages16
Volume5254
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 → …

Fingerprint

Probability distributions
Information theory

Bibliographical note

© Springer-Verlag Berlin Heidelberg 2008

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). Berlin. https://doi.org/10.1007/978-3-540-87987-9_15
Chernov, Alexey ; Shen, Alexander ; Vereshchagin, Nikolai ; Vovk, Vladimir. / On-Line Probability, Complexity and Randomness. 19th International Conference, ALT 2008. Vol. 5254 Berlin, 2008. pp. 138-153 (Lecture Notes in Computer Science).
@inproceedings{24e5f5a7936446a39c8fe0a0da533e87,
title = "On-Line Probability, Complexity and Randomness",
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.",
author = "Alexey Chernov and Alexander Shen and Nikolai Vereshchagin and Vladimir Vovk",
note = "{\circledC} Springer-Verlag Berlin Heidelberg 2008",
year = "2008",
month = "12",
day = "31",
doi = "10.1007/978-3-540-87987-9_15",
language = "English",
isbn = "9783540879862",
volume = "5254",
series = "Lecture Notes in Computer Science",
pages = "138--153",
booktitle = "19th International Conference, ALT 2008",

}

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

On-Line Probability, Complexity and Randomness. / Chernov, Alexey; Shen, Alexander; Vereshchagin, Nikolai; Vovk, Vladimir.

19th International Conference, ALT 2008. Vol. 5254 Berlin, 2008. p. 138-153 (Lecture Notes in Computer Science).

Research output: Chapter in Book/Conference proceeding with ISSN or ISBNConference contribution with ISSN or ISBNResearchpeer-review

TY - GEN

T1 - On-Line Probability, Complexity and Randomness

AU - Chernov, Alexey

AU - Shen, Alexander

AU - Vereshchagin, Nikolai

AU - Vovk, Vladimir

N1 - © Springer-Verlag Berlin Heidelberg 2008

PY - 2008/12/31

Y1 - 2008/12/31

N2 - 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.

AB - 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.

U2 - 10.1007/978-3-540-87987-9_15

DO - 10.1007/978-3-540-87987-9_15

M3 - Conference contribution with ISSN or ISBN

SN - 9783540879862

VL - 5254

T3 - Lecture Notes in Computer Science

SP - 138

EP - 153

BT - 19th International Conference, ALT 2008

CY - Berlin

ER -

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