inria-00606457, version 4
The dimension of ergodic random sequences
STACS (2012)
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 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.
- 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 4
- http://hal.inria.fr/inria-00606457
- oai:hal.inria.fr:inria-00606457
- Contributeur :
- Soumis le : Jeudi 21 Juillet 2011, 09:38:24
- Dernière modification le : Mardi 29 Novembre 2011, 13:48:41
Documents associés
Exporter