Ornstein Isomorphism and Algorithmic Randomness
Preprint
Abstract
In 1970, Donald Ornstein proved a landmark result in dynamical systems, viz., two Bernoulli systems with the same entropy are isomorphic except for a measure 0 set. Keane and Smorodinsky gave a finitary proof of this result. They also indicated how one can generalize the result to mixing Markov Shifts. We adapt their construction to show that if two computable mixing Markov systems have the same entropy, then there is a layerwise computable isomorphism defined on all Martin-Lof random points in the system. Since the set of Martin-Lof random points forms a measure 1 set, it implies the classical result for such systems. This result uses several recent developments in computable analysis and algorithmic randomness. Following the work by Braverman, Nandakumar, and Hoyrup and Rojas introduced discontinuous functions into the study of algorithmic randomness. We utilize Hoyrup and Rojas' elegant notion of layerwise computable functions to produce the test of randomness in our result. Further, we use the recent result of the effective Shannon-McMillan-Breiman theorem, independently established by Hochman and Hoyrup to prove the properties of our construction. We show that the result cannot be improved to include all points in the systems - only trivial computable isomorphisms exist between systems with the same entropy.Keywords
All Related Versions
This publication has 11 references indexed in Scilit:
- L1-Computability, Layerwise Computability and Solovay ReducibilityComputability, 2013
- Upcrossing inequalities for stationary sequences and applicationsThe Annals of Probability, 2009
- A constructive Borel–Cantelli lemma. Constructing orbits with required statistical propertiesTheoretical Computer Science, 2009
- Uniform test of algorithmic randomness over a general spaceTheoretical Computer Science, 2005
- Ergodic theorems for individual random sequencesTheoretical Computer Science, 1998
- The interactions between ergodic theory and information theoryIEEE Transactions on Information Theory, 1998
- The Law of the Iterated Logarithm for Random Kolmogorov, or Chaotic, SequencesTheory of Probability & Its Applications, 1988
- Bernoulli Schemes of the Same Entropy are Finitarily IsomorphicAnnals of Mathematics, 1979
- The finitary isomorphism theorem for Markov shiftsBulletin of the American Mathematical Society, 1979
- Bernoulli shifts with the same entropy are isomorphicAdvances in Mathematics, 1970