On-Line Probability, Complexity and Randomness

Alexey Chernov, Alexander Shen, Nikolai Vereshchagin, Vladimir Vovk

    Research output: Chapter in Book/Report/Conference proceedingConference 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.
    LanguageEnglish
    Title of host publication19th International Conference, ALT 2008
    Place of PublicationBerlin
    Pages138-153
    Number of pages16
    Volume5254
    DOIs
    StatePublished - 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. DOI: 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. DOI: 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/Report/Conference proceedingConference contribution with ISSN or ISBN

    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). Available from, DOI: 10.1007/978-3-540-87987-9_15