×

zbMATH — the first resource for mathematics

The weight-per-symbol polytope and scaffolds of invariants associated with Markov chains. (English) Zbl 0725.60071
The weight along a periodic orbit in a Markov chain is the product of the transition probabilities along the edges of the cycle in the corresponding directed graph. Using invariants based on these weights the authors show that there is a constraint on the degree of a finite-to-one block homomorphism from one Markov chain to another. The authors consider the average weight per symbol of each periodic orbit as an element of a rational vector space. The convex hull is called the weight-per-symbol polytope of the Markov chain. This polytope allows the construction of canonically-defined induced Markov chains inside the original Markov chains, whose own invariants in turn give a “scaffold” of invariants for the original Markov chain. Using these invariants the authors construct counterexamples to the conjecture of W. Parry and S. Tuncel [ibid. 1, 303-335 (1981; Zbl 0485.60063)] that the \(\beta\)- function is a complete invariant of finite equivalence. They also show that “almost block isomorphism” and “finitary isomorphism with finite expected code length” are not the same. There are also some results about the minimality (with respect to block homomorphism) of a Bernoulli shift in the class of Markov chains whose \(\beta\)-function equals the \(\beta\)-function of the Bernoulli shift.

MSC:
60J10 Markov chains (discrete-time Markov processes on discrete state spaces)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] DOI: 10.1016/0024-3795(86)90120-5 · Zbl 0588.15015
[2] del Junco, Prog. Math. 10 pp 91– (1981)
[3] Boyle, Memoirs Amer. Math. Soc. none pp none– (1987)
[4] Block, Periodic points and topological entropy of one-dimensional maps pp 18–
[5] Ashley, Ergod. Th. & Dynam. Sys. 10 pp none– (1990)
[6] Adler, Memoirs Amer. Math. Soc. 219 pp none– (1979)
[7] Adler, Ergod. Th. & Dynam. Sys. 5 pp 485– (1985)
[8] DOI: 10.2307/2044261 · Zbl 0483.58010
[9] Shannon, Bell. Sys. Tech. J. 27 pp 379– (1948) · Zbl 1154.94303
[10] Seneta, Non-negative Matrices and Markov Chains (1981) · Zbl 1099.60004
[11] DOI: 10.1112/blms/14.1.16 · Zbl 0481.28015
[12] Parry, Ergod. Th. & Dynam. Sys. 1 pp 303– (1981)
[13] DOI: 10.1007/BF01388488 · Zbl 0563.28008
[14] Parry, Problems and perspectives in the theory of Markov shifts pp 626– · Zbl 0661.54040
[15] Nasu, Ergod. Th. & Dynam. Sys. 3 pp 387– (1983)
[16] DOI: 10.1007/BF00532486 · Zbl 0516.60075
[17] Kitchens, On measures induced on subsystems pp 455–
[18] Kitchens, Contemp. Math. 26 pp 231– (1981) · Zbl 0534.28008
[19] DOI: 10.1016/0012-365X(82)90141-8 · Zbl 0481.05046
[20] Handelman, Positive polynomials, convex integral polytopes, and a random walk problem (1987) · Zbl 0654.46059
[21] Handelman, Ergod. Th. & Dynam. Sys. 6 pp 57– (1986)
[22] Kitchens, Memoirs Amer. Math. Soc. 338 pp none– (1985)
[23] DOI: 10.2307/1970908 · Zbl 0282.58008
[24] Walters, An Introduction to Ergodic Theory (1982) · Zbl 0475.28009
[25] DOI: 10.1112/plms/s3-46.1.100 · Zbl 0544.28011
[26] DOI: 10.1007/BF02762856 · Zbl 0472.28016
[27] DOI: 10.1007/BF01388489 · Zbl 0563.28009
[28] Kim, Informal. Syst. Sci. 4 pp 123– (1979)
[29] DOI: 10.1007/BF01762187 · Zbl 0309.54032
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.