An Invariant Of Finitary Codes With Finite Expected Square Root Coding Length

Let \(p\) and \(q\) be probability vectors with the same entropy \(h\). Denote by \(B(p)\) the Bernoulli shift indexed by \(\Z\) with marginal distribution \(p\). Suppose that \(\phi\) is a measure preserving homomorphism from \(B(p)\) to \(B(q)\). We prove that if the coding length of \(\phi\) has a finite 1/2 moment, then \({\sigma }_2^p={\sigma }_2^q\), where \({\sigma }_2^p={\sum }_ip_i(-logp_i-h)_2\) is the {\dof informational variance} of \(p\). In this result, which sharpens a theorem of Parry (1979), the 1/2 moment cannot be replaced by a lower moment. On the other hand, for any \(\theta <1\), we exhibit probability vectors \(p\) and \(q\) that are not permutations of each other, such that there exists a finitary isomorphism \(\Phi\) from \(B(p)\) to \(B(q)\)where the coding lengths of \(\Phi\) and of its inverse have a finite \(\theta\) moment. We also present an extension to ergodic Markov chains.