Skip to Main content Skip to Navigation

Ex-Post Algorithmic Probability

J-L. 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 metadatas
Contributor : Telecomparis Hal <>
Submitted on : Friday, September 13, 2019 - 4:38:08 PM
Last modification on : Tuesday, March 24, 2020 - 9:52:04 AM


  • HAL Id : hal-02287136, version 1



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



Record views