The dimension of ergodic random sequences


الملخص بالإنكليزية

Let mu be a computable ergodic shift-invariant measure over the Cantor space. Providing a constructive proof of Shannon-McMillan-Breiman theorem, Vyugin proved that if a sequence x is Martin-Lof 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 Birkhoffs ergodic theorem for Martin-Lof random sequences.

تحميل البحث