inria-00606457, version 2
The dimension of ergodic random sequences
(2011)
Résumé : Let \mu be a computable ergodic shift-invariant measure over the Cantor space. Providing a constructive proof of Shannon-McMillan-Breiman theorem, V'yugin proved that if a sequence x is Martin-Löf random w.r.t. \mu then the strong effective dimension Dim(x) of x equals the entropy of \mu. Whether its effective dimension dim(x) also equals the entropy was left as an problem question. 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.
- a – INRIA
- 1 :
- CNRS : UMR7503 – INRIA – Université de Lorraine
- Domaine : Informatique/Théorie de l'information et codage
Mathématiques/Théorie de l'information et codage - Mots-clés : Shannon-McMillan-Breiman theorem – Martin-Löf random sequence – effective Hausdorff dimension – compression rate – entropy
- Versions disponibles : v1 (06-07-2011) v2 (06-07-2011) v3 (11-07-2011) v4 (21-07-2011)
- inria-00606457, version 2
- http://hal.inria.fr/inria-00606457
- oai:hal.inria.fr:inria-00606457
- Contributeur :
- Soumis le : Mercredi 6 Juillet 2011, 16:07:07
- Dernière modification le : Lundi 11 Juillet 2011, 15:37:30
Documents associés
Exporter