Hostname: page-component-586b7cd67f-t7czq Total loading time: 0 Render date: 2024-12-01T02:10:58.145Z 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: [email protected])
YUVAL PERES
Affiliation:
Microsoft Research, Redmond, WA and UC Berkeley, CA 94720, USA (email: [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

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.

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

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

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