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
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)
† Partially supported by NSF Grant DMS-8803260.