Randomness and Ergodic Theory: An Algorithmic Point of View

Abstract

The first of our two main goals is investigating the relation between the notions of algorithmic randomness and dynamical typicalness. The former express the “algorithmic unpredictability” of individual infinite sequences with respect to a given probability measure and is modeled with the tools of computability theory. The latter, usually modeled in the framework of ergodic theory/dynamical systems, express the “physical plausibility” of an initial condition with respect to its evolution under some dynamics (a physically plausible point should follow the “expected” or “typical” behaviour of the system). Roughly, the motivation is the following: absolutely complete knowledge of the state of a physical system is unattainable (for many reasons). Now, supposing we access the physical world by “algorithmic means” (measurements are always finite approximations possibly elaborated later in computers) then it makes sense to modelize a “physical” point as being “algorithmically unknownable”. To study this, it is essential to develop algorithmic tools adapted to the usual context in which ergodic theory takes place and this is what the entire first part of this thesis is devoted to. Then we consider two notions of algorithmic randomness due to Martin-Löf and Schnorr and prove three main results, thus establishing the relationship with typicality. i) In any computable metric space with an arbitrary probability measure μ, there always exists a universal uniform Martin-Löf-randomness test; ii) If μ is computable, then the trajectory of a Martin-Löf random point under any computable ergodic dynamics always follow the typical statistical behaviour of the system; iii) A point is Schnorr random if and only if its trajectory follows the typical behaviour of any computable mixing dynamics. As a second goal we study from a highly theoretical point of view the problem of simulating randomness or typical statistical behaviours on a computer, with a particular interest in the ergodic behaviour of dynamical systems. We prove that for several classes of dynamical systems having a single “physically relevant” invariant measure, i) this measure is computable and ii) there exist computable points (the only ones we have access in computer simulations) following the typical behaviour of the system. As a direct application we obtain the existence of computable reals which are Borel-normal with respect to any base.