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

1 March 1991

journal article
research article
Published by Cambridge University Press (CUP) in Ergodic Theory and Dynamical Systems

Vol. 11 (1) , 129-180
https://doi.org/10.1017/s0143385700006052

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.

Keywords

MARKOV CHAIN

This publication has 26 references indexed in Scilit:

Resolving maps and the dimension group for shifts of finite type
Memoirs of the American Mathematical Society, 1987
Deciding eventual positivity of polynomials
Ergodic Theory and Dynamical Systems, 1986
Almost topological classification of finite-to-one factor maps between shifts of finite type
Ergodic Theory and Dynamical Systems, 1985
Finitary measures for subshifts of finite type and sofic systems
Memoirs of the American Mathematical Society, 1985
Invariants for finitary isomorphisms with finite expected code lengths
Inventiones Mathematicae, 1984
Natural coefficients and invariants for Markov-shifts
Inventiones Mathematicae, 1984
An Invariant for Continuous Factors of Markov Shifts
Proceedings of the American Mathematical Society, 1981
On the classification of Markov chains by finite equivalence
Ergodic Theory and Dynamical Systems, 1981
Topological entropy and equivalence of dynamical systems
Memoirs of the American Mathematical Society, 1979
Endomorphisms of irreducible subshifts of finite type
Theory of Computing Systems, 1974