A constructive version of Birkhoff's ergodic theorem for Martin-Lof random points

Abstract : A theorem of Kucera states that given a Martin-Löf random infinite binary sequence {\omega} and an effectively open set A of measure less than 1, some tail of {\omega} is not in A. We first prove several results in the same spirit and generalize them via an effective version of a weak form of Birkhoff's ergodic theorem. We then use this result to get a stronger form of it, namely a very general effective version of Birkhoff's ergodic theorem, which improves all the results previously obtained in this direction, in particular those of V'Yugin, Nandakumar and Hoyrup, Rojas.
Liste complète des métadonnées

Littérature citée [10 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00643629
Contributeur : Mathieu Hoyrup <>
Soumis le : mardi 22 novembre 2011 - 14:20:24
Dernière modification le : jeudi 24 mai 2018 - 15:59:23
Document(s) archivé(s) le : vendredi 16 novembre 2012 - 11:45:37

Fichier

ergodic-edited.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

Laurent Bienvenu, Adam Day, Mathieu Hoyrup, Ilya Mezhirov, Alexander Shen. A constructive version of Birkhoff's ergodic theorem for Martin-Lof random points. Information and Computation, Elsevier, 2012, 210, pp.021-030. 〈http://www.sciencedirect.com/science/article/pii/S0890540111001465〉. 〈10.1016/j.ic.2011.10.006〉. 〈hal-00643629〉

Partager

Métriques

Consultations de la notice

677

Téléchargements de fichiers

182