License: Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2012.567
URN: urn:nbn:de:0030-drops-33917
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2012/3391/
Go to the corresponding LIPIcs Volume Portal

Hoyrup, Mathieu

The dimension of ergodic random sequences

pdf-format:
7.pdf (0.6 MB)

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.

BibTeX - Entry

@InProceedings{hoyrup:LIPIcs:2012:3391,
  author =	{Mathieu Hoyrup},
  title =	{{The dimension of ergodic random sequences}},
  booktitle =	{29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)},
  pages =	{567--576},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-35-4},
  ISSN =	{1868-8969},
  year =	{2012},
  volume =	{14},
  editor =	{Christoph D{\"u}rr and Thomas Wilke},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2012/3391},
  URN =		{urn:nbn:de:0030-drops-33917},
  doi =		{10.4230/LIPIcs.STACS.2012.567},
  annote =	{Keywords: Shannon-McMillan-Breiman theorem, Martin-L{\"o}f random sequence, effective Hausdorff dimension, compression rate, entropy }
}

Keywords: Shannon-McMillan-Breiman theorem, Martin-Löf random sequence, effective Hausdorff dimension, compression rate, entropy
Collection: 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)
Issue Date: 2012
Date of publication: 24.02.2012

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI