Hostname: page-component-cd9895bd7-lnqnp Total loading time: 0 Render date: 2024-12-26T01:17:35.299Z Has data issue: false hasContentIssue false
  • English
  • Français

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

Published online by Cambridge University Press:  19 September 2008

Brian Marcus  and
Selim Tuncel
Brian Marcus
Affiliation:
IBM Almaden Research Center, K65-802, 650 Harry Rd, San Jose, CA 95120, USA
Selim Tuncel
Affiliation:
Mathematics Department, University of Washington, Seattle, Washington 98195, USA
Get access Rights & Permissions [Opens in a new window]

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.

Type
Research Article
Information
Ergodic Theory and Dynamical Systems , Volume 11 , Issue 1 , March 1991 , pp. 129 - 180
Copyright
Copyright © Cambridge University Press 1991

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

REFERENCES

[1]Adler, R. & Marcus, B.. Topological entropy and equivalence of dynamical systems. Memoirs Amer. Math. Soc. 219 (1979).Google Scholar
[2]Ashley, J.. Bounded-to-1 factors of an aperiodic shift of finite type are 1-to-l almost everywhere factors also. Ergod. Th. & Dynam. Sys. 10 (1990).CrossRefGoogle Scholar
[3]Block, L., Guckenheimer, J., Misurewicz, M. & Young, L.. Periodic points and topological entropy of one-dimensional maps. Lecture Notes in Math. 819, Springer: New York, pp. 18–34.Google Scholar
[4]Boyle, M., Marcus, B. & Trow, P.. Resolving maps and the dimension group for shifts of finite type, Mem. Memoirs Amer. Math. Soc. (1987).CrossRefGoogle Scholar
[5]Coven, E. & Paul, M.. Endomorphisms of irreducible shifts of finite type. Math. Sys. Theory 8 (1974), 167–175.CrossRefGoogle Scholar
[6]Friedland, S.. Limit eigenvalues of nonnegative matrices. L. Alg. Appl. 74 (1986), 173–178.CrossRefGoogle Scholar
[7]Handelman, D.. Eventual positivity and finite equivalence for matrices of polynomials. Preprint.Google Scholar
[8]del Junco, A., Keane, M., Kitchens, B., Marcus, B. & Swanson, L.. Continuous homomorphisms of Bernoulli schemes. Prog. Math. 10 (1981), 91–111.CrossRefGoogle Scholar
[9]Kim, K. & Roush, F.. Some results on the decidability of shift equivalence, J. of Combinatorics. Informal. Syst. Sci. 4 (1979), 123–146.Google Scholar
[10]Kitchens, B.. Linear algebra and subshifts of finite type. Contemp. Math. 26 (1981), 231–248.CrossRefGoogle Scholar
[11]Kitchens, B. & Tuncel, S.. On measures induced on subsystems. Lecture Notes in Math. 1342, Springer: New York, pp. 455–464.Google Scholar
[12]Krieger, W.. On the finitary isomorphisms of Markov shifts that have finite expected coding time. Z. Wahr. 65 (1983), 323–328.CrossRefGoogle Scholar
[13]Nasu, M.. Constant-to-one and onto global maps of homomorphisms between strongly connected graphs. Ergod. Th. & Dynam. Sys. 3 (1983), 387–414.CrossRefGoogle Scholar
[14]Parry, W.. Problems and perspectives in the theory of Markov shifts. Lecture Notes in Math. 1342, Springer: New York, pp. 626–637.Google Scholar
[15]Parry, W. & Schmidt, K.. Natural coefficients and invariants for Markov shifts. Invent. Math. 76 (1984), 15–32.CrossRefGoogle Scholar
[16]Parry, W. & Tuncel, S.. On the classification of Markov chains by finite equivalence. Ergod. Th. & Dynam. Sys. 1 (1981), 303–335.CrossRefGoogle Scholar
[17]Parry, W. & Tuncel, S.. On the stochastic and topological structure of Markov chains. Bull. London Math. Soc. 14 (1982), 16–27.CrossRefGoogle Scholar
[18]Seneta, E.. Non-negative Matrices and Markov Chains. Springer: New York, 1981.CrossRefGoogle Scholar
[19]Shannon, C.. A mathematical theory of communication. Bell. Sys. Tech. J. 27 (1948), 379–423; 623–656.CrossRefGoogle Scholar
[20]Schmidt, K.. Invariants for finitary isomorphisms with finite expected code lengths. Invent. Math. 76 (1984), 33–40.CrossRefGoogle Scholar
[21]Tuncel, S.. Conditional pressure and coding. Israel J. Math. 39 (1981), 101–112.CrossRefGoogle Scholar
[22]Tuncel, S.. A dimension, dimension modules and Markov chains. Proc. London Math. Soc. 46 (1983), 100–116.CrossRefGoogle Scholar
[23]Walters, P.. An Introduction to Ergodic Theory. Springer: New York, 1982.CrossRefGoogle Scholar
[24]Williams, R.. Classification of shifts of finite type. Ann. Math. 98 (1973), 120–153; Errata, Ann. Math. 99 (1974), 380–381.CrossRefGoogle Scholar
[25]Kitchens, B. & Tuncel, S.. Finitary measures for subshifts of finite type and sofic systems. Memoirs Amer. Math. Soc. 338 (1985).Google Scholar
[26]Handelman, D.. Deciding eventual positivity of polynomials. Ergod. Th. & Dynam. Sys. 6 (1986), 57–79.CrossRefGoogle Scholar
[27]Handelman, D.. Positive polynomials, convex integral polytopes, and a random walk problem. Lecture Notes in Math. 1282. Springer-Verlag: New York and Heidelberg, 1987.CrossRefGoogle Scholar
[28]Parry, W.. Notes on coding problems for finite state processes. Preprint, 1989.Google Scholar
[29]Nasu, M.. Uniformly finite-to-one and onto extensions of homomorphisms between strongly connected graphs. Discrete Math. 39 (1982), 171–197.CrossRefGoogle Scholar
[30]Kitchens, B.. An invariant for continuous factors of Markov shifts. Proc. Amer. Math. Soc. 83 (1981), 825–828.CrossRefGoogle Scholar
[31]Adler, R., Kitchens, B. & Marcus, B. Almost topological classification of finite-to-one factor maps between shifts of finite type. Ergod. Th. & Dynam. Sys. 5 (1985), 485–500.CrossRefGoogle Scholar