Ergodic Theory and Dynamical Systems

Research Article

The weight-per-symbol polytope and scaffolds of invariants associated with Markov chains

Brian Marcusa1 and Selim Tuncela2

a1 IBM Almaden Research Center, K65-802, 650 Harry Rd, San Jose, CA 95120, USA

a2 Mathematics Department, University of Washington, Seattle, Washington 98195, USA

Abstract

We study Markov chains via invariants constructed from periodic orbits. Canonical extensions, based on these invariants, are used to establish a constraint on the degree of finite-to-one block homomorphisms from one Markov chain to another. We construct a polytope from the normalized weights of periodic orbits. Using this polytope, we find canonically-defined induced Markov chains inside the original Markov chain. Each of the invariants associated with these Markov chains gives rise to a scaffold of invariants for the original Markov chain. This is used to obtain counterexamples to the finite equivalence conjecture and to a conjecture regarding finitary isomorphism with finite expected coding time. Also included are results related to the problem of minimality (with respect to block homomorphism) of Bernoulli shifts in the class of Markov chains with beta function equal to the beta function of the Bernoulli shift.

(Received April 21 1989)

(Revised January 01 1990)

Footnotes

† Partially supported by NSF Grant DMS-8803260.