Skip to Main content Skip to Navigation

Ex-Post Algorithmic Probability

Jean-Louis Dessalles 1, 2 
1 DIG - Data, Intelligence and Graphs
LTCI - Laboratoire Traitement et Communication de l'Information
Abstract : Algorithmic probability is traditionally defined by considering the output of a universal machine fed with random programs. This definition proves inappropriate for many practical applications where probabilistic assessments are spontaneously and instantaneously performed. In particular, it does not tell what aspects of a situation are relevant when considering its probability ex-post (after its occurrence). As it stands, the standard definition also fails to capture the fact that simple, rather than complex outcomes are often considered improbable, as when a supposedly random device produces a repeated pattern. More generally, the standard algorithmic definition of probability conflicts with the idea that entropy maximum corresponds to states that are both complex (unordered) and probable. We suggest here that algorithmic probability should rather be defined as a difference in complexity. We distinguish description complexity from generation complexity. Improbable situations are situations that are more complex to generate than to describe. We show that this definition is more congruent with the intuitive notion of probability.
Complete list of metadata
Contributor : TelecomParis HAL Connect in order to contact the contributor
Submitted on : Friday, September 13, 2019 - 4:38:08 PM
Last modification on : Tuesday, October 19, 2021 - 11:14:16 AM


  • HAL Id : hal-02287136, version 1



Jean-Louis Dessalles. Ex-Post Algorithmic Probability. [Research Report] 2011-D-009, Télécom ParisTech. 2011. ⟨hal-02287136⟩



Record views