Randomness and the ergodic decomposition Mathieu Hoyrup

Abstract. We briefly present ongoing work about Martin-Löf randomness and the ergodic decompo-sition theorem. In [ML66], Martin-Löf defined the notion of an algorithmically random infinite binary sequence. The idea was to have an individual notion of a random object, an object that is acceptable as an outcome of a probabilistic process (typically, the tossing of a coin). This no-tion has proved successful, as it turns out that random sequences in the sense of Martin-Löf have all the usual properties that are proved to hold almost surely in classical probability theory. A particularly interesting property is typicalness in the sense of Birkhoff’s ergodic theorem. This theorem embodies many probability theorems (strong law of large numbers, diophantine approximation, e.g.). Whereas the algorithmic versions of many probability the-orems are straightforward to derive from their classical proofs, whether the ergodic theorem has a version for random elements has been an open problem for years, finally proved by V’yugin [V’y97] (improvements of this result, extending the class of functions for which the algorithmic version holds, have been established later in [Nan08], [HR09]). The reason for this difficulty is that the classical proof of Birkhoff’s theorem is in some sense nonconstructive