Hostname: page-component-7b7567c8c-wxvwp Total loading time: 0 Render date: 2026-11-13T21:52:38.631Z Has data issue: false hasContentIssue false
  • English
  • Français

An invariant of finitary codes with finite expected square root coding length

Published online by Cambridge University Press:  18 January 2010

NATE HARVEY and
YUVAL PERES
NATE HARVEY
Affiliation:
Department of Mathematics, UC Berkeley CA, 94720, USA (email: nathaniel.e.harvey@jpl.nasa.gov)
YUVAL PERES
Affiliation:
Microsoft Research, Redmond, WA and UC Berkeley, CA 94720, USA (email: peres@microsoft.com)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

Let p and q be probability vectors with the same entropy h. Denote by B(p) the Bernoulli shift indexed by ℤ with marginal distribution p. Suppose that φ is a measure-preserving homomorphism from B(p) to B(q). We prove that if the coding length of φ has a finite 1/2 moment, then σ2p=σ2q, where σ2p=∑ ipi(−log  pi−h)2 is the informational variance of p. In this result, the 1/2 moment cannot be replaced by a lower moment. On the other hand, for any θ<1, we exhibit probability vectors p and q that are not permutations of each other, such that there exists a finitary isomorphism Φ from B(p) to B(q) where the coding lengths of Φ and of its inverse have a finite θ moment. We also present an extension to ergodic Markov chains.

Information

Type
Research Article
Information
Ergodic Theory and Dynamical Systems , Volume 31 , Issue 1 , February 2011, pp. 77 - 90
Copyright
Copyright © Cambridge University Press 2009

References

[1]Durrett, R.. Probability: Theory and Examples, 2nd edn. Duxbury Press, New York, 1996.Google Scholar
[2]Gordin, M. I. and Lifšic, B. A.. The central limit theorem for stationary Markov processes. Soviet Math. Dokl. 19 (1978), 392–394.Google Scholar
[3]Keane, M. and Smorodinsky, M.. Bernoulli schemes of the same entropy are finitarily isomorphic. Ann. of Math. (2) 109 (1979), 397–406.CrossRefGoogle Scholar
[4]Liggett, T.. Tagged particle distributions or how to choose a head at random. In and Out of Equilibrium (Mambucaba, 2000) (Progress in Probability, 51). Birkhäuser, Boston, 2002, pp. 133–162.CrossRefGoogle Scholar
[5]Meshalkin, L. D.. A case of isomorphism of Bernoulli schemes. Dokl. Akad. Nauk SSSR 128 (1959), 41–44.Google Scholar
[6]Ornstein, D. S.. Bernoulli shifts of the same entropy are isomorphic. Adv. Math. 4 (1970), 337–352.CrossRefGoogle Scholar
[7]Parry, W.. Finitary isomorphisms with finite expected code lengths. Bull. Lond. Math. Soc. 11 (1979), 170–176.CrossRefGoogle Scholar
[8]Parry, W.. An information obstruction to finite expected coding length. Ergodic Theory (Proc. Conf., Math. Forschungsinst., Oberwolfach, 1978) (Lecture Notes in Mathematics, 729). Springer, Berlin, 1979, pp. 163–168.Google Scholar
[9]Parry, W. and Schmidt, K.. Invariants of finitary isomorphisms with finite expected code-lengths. Conference in Modern Analysis and Probability (New Haven, Conn., 1982) (Contemporary Mathematics, 26). American Mathematical Society, Providence, RI, 1984, pp. 301–307.CrossRefGoogle Scholar
[10]Parry, W. and Tuncel, S.. Classification Problems in Ergodic Theory (London Mathematical Society Lecture Note Series, 67). Cambridge University Press, Cambridge, 1982, p. 1.CrossRefGoogle Scholar
[11]Petersen, K.. Ergodic Theory. Cambridge University Press, Cambridge, 1983.CrossRefGoogle Scholar
[12]Schmidt, K.. Invariants for finitary isomorphisms with finite expected code lengths. Invent. Math. 76 (1984), 33–40.CrossRefGoogle Scholar
[13]Stroock, D. W.. Probability Theory, An Analytic View. Cambridge University Press, Cambridge, 1993.Google Scholar