The dimension of ergodic random sequences

DOI10.4230/LIPICS.STACS.2012.567MaRDI QIDQ2904794zbMATH OpenOpenAlexFDO

Authors Mathieu Hoyrup

Publication date 23 August 2012

Full work available at URL https://arxiv.org/abs/1107.1149

zbMATH Keywords

compression rateeffective Hausdorff dimensionentropyMartin-Löf random sequenceShannon-McMillan-Breiman theorem

Mathematics Subject Classification ID

Algorithmic randomness and dimension (03D32) Constructive and recursive analysis (03F60) Hausdorff and packing measures (28A78) Ergodic theorems, spectral theory, Markov operators (37A30)

Abstract: 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"of 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"of random sequences.

Recommendations

• Ergodic theorems for individual random sequences
• scientific article; zbMATH DE number 1670880
• Ergodic-Type Characterizations of Algorithmic Randomness
• A constructive version of Birkhoff's ergodic theorem for Martin-Löf random points
• The dimensions of individual strings and sequences

Cited in

(12)

• Computability theory. Abstracts from the workshop held January 7--13, 2018
• Randomness and initial segment complexity for measures
• Martin-Löf randomness implies multiple recurrence in effectively closed sets
• A divergence formula for randomness and dimension
• Эффективная сходимость по вероятности и эргодическая теорема для индивидуальных случайных последовательностей
• A constructive version of Birkhoff's ergodic theorem for Martin-Löf random points
• Computable Measure Theory and Algorithmic Randomness
• Universal coding and prediction on ergodic random points
• Martin-Löf random quantum states
• Randomness extraction in computability theory
• Ergodic theorems and converses for PSPACE functions
• Vladimir V'yugin: short biography and some research contributions

This page was built for publication: The dimension of ergodic random sequences

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2904794)