Game-theoretic approaches to randomness: unpredictability and stochasticity.
Laurent Bienvenu · HAL (Le Centre pour la Communication Scientifique Directe) · 2008
This thesis is a contribution to the study of the different notions of effective randomness for individual ob jects (mainly binary sequences, finite or infinite). In the first chapter, we consider various game-theoretic approaches to randomness (via martingales and strategies), and we compare them to the historical approach by frequency stability, which goes back to the work of von Mises in the beginning of the 20th century. The principal result of the first chapter is an explicit relation between the ?speed of success? of a martingale (or strategy) on a sequence and the bias of the selected subsequences. The second chapter focuses on the links between the various randomness notions for infinite sequences and the notion of Kolmogorov complexity (or program-size complexity), defined to be the size of the shortest program which outputs a given finite ob ject. Many results are already known in this direction. We present a new approach, using computable upper bounds of Kolmogorov complexity instead of Kolmogorov complexity itself. This turns out to be a very unifying approach, in the sense that it allows us to characterize a wide variety of randomness notions, even some for which Kolmogorov complexity fails. The third and last chapter studies the extension of all randomness notions to wider classes of probability measures, and more specifically the equivalence relations induced by the randomness notions (where we say that two measures are equivalent if they have the same random sequences). A constructive proof of Kakutani?s theorem (a criterion of equivalence for generalized Bernoulli measures) is presented. Finally, in great generality (i.e. for arbitrary computable measures), we give a complete hierarchical classification of the induced equivalence relations.