The dimension of ergodic random sequences

Mathieu Hoyrup 1, *
* Auteur correspondant
1 CARTE - Theoretical adverse computations, and safety
Inria Nancy - Grand Est, LORIA - FM - Department of Formal Methods
Abstract : Let m be a computable ergodic shift-invariant measure over the set of infinite binary sequences. Providing a constructive proof of Shannon-McMillan-Breiman theorem, V'yugin proved that if x is a Martin-Löf random binary sequence w.r.t. m then its strong effective dimension Dim(x) equals the entropy of m. Whether its effective dimension dim(x) also equals the entropy was left as an open problem. In this paper we settle this problem, providing a positive answer. A key step in the proof consists in extending recent results on Birkhoff's ergodic theorem for Martin-Löf random sequences. At the same time, we present extensions of some previous results. As pointed out by a referee the main result can also be derived from results by Hochman [Upcrossing inequalities for stationary sequences and applications. The Annals of Probability, 37(6):2135--2149, 2009], using rather different considerations.
Type de document :
Communication dans un congrès
Christoph Dürr and Thomas Wilke. STACS'12 (29th Symposium on Theoretical Aspects of Computer Science), Feb 2012, Paris, France. LIPIcs, 14, pp.567-576, 2011
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00606457
Contributeur : Mathieu Hoyrup <>
Soumis le : jeudi 21 juillet 2011 - 09:38:24
Dernière modification le : jeudi 11 janvier 2018 - 06:21:25
Document(s) archivé(s) le : dimanche 4 décembre 2016 - 14:58:38

Fichiers

paperbiblio.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00606457, version 4
  • ARXIV : 1107.1149

Collections

Citation

Mathieu Hoyrup. The dimension of ergodic random sequences. Christoph Dürr and Thomas Wilke. STACS'12 (29th Symposium on Theoretical Aspects of Computer Science), Feb 2012, Paris, France. LIPIcs, 14, pp.567-576, 2011. 〈inria-00606457v4〉

Partager

Métriques

Consultations de la notice

282

Téléchargements de fichiers

136