Remote Access Electronic Research Announcements

Electronic Research Announcements

ISSN 1079-6762



Powers of positive polynomials and codings of Markov chains onto Bernoulli shifts

Authors: Brian Marcus and Selim Tuncel
Journal: Electron. Res. Announc. Amer. Math. Soc. 5 (1999), 91-101
MSC (1991): Primary 28D20; Secondary 11C08, 05A10
Published electronically: June 30, 1999
MathSciNet review: 1696825
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We give necessary and sufficient conditions for a Markov chain to factor onto a Bernoulli shift (i) as an eventual right-closing factor, (ii) by a right-closing factor map, (iii) by a one-to-one a.e. right-closing factor map, and (iv) by a regular isomorphism. We pass to the setting of polynomials in several variables to represent the Bernoulli shift by a nonnegative polynomial $p$ in several variables and the Markov chain by a matrix $A$ of such polynomials. The necessary and sufficient conditions for each of (i)-(iv) involve only an eigenvector $r$ of $A$ and basic invariants obtained from weights of periodic orbits. The characterizations of (ii)-(iv) are deduced from (i). We formulate (i) as a combinatorial problem, reducing it to certain state-splittings (partitions) of paths of length $n$. In terms of positive polynomial masses associated with paths, the aim then becomes the construction of partitions so that the masses of the paths in each partition element sum to a multiple of $p^n$, the multiple being prescribed by $r$. The construction, which we sketch, relies on a description of the terms of $p^n$ and on estimates of the relative sizes of the coefficients of $p^n$.

References [Enhancements On Off] (What's this?)

  • [A] J. Ashley, Resolving factor maps for shifts of finite type with equal entropy, Ergod. Th. and Dynam. Sys. 11 (1991), 219-240. MR 92d:58056
  • [AMT] J. Ashley, B. Marcus and S. Tuncel, The classification of one-sided Markov chains, Ergod. Th. and Dynam. Sys. 17 (1997), 269-295. MR 98k:28021
  • [BMT] M. Boyle, B. Marcus and P. Trow, Resolving maps and the dimension group for shifts of finite type, Mem. Amer. Math. Soc. 377 (1987). MR 89c:28019
  • [BT] M. Boyle and S. Tuncel, Regular isomorphism of Markov chains is almost topological, Ergod. Th. and Dynam. Sys. 10 (1990), 89-100. MR 92i:28021
  • [H] D. Handelman, Positive polynomials and product type actions of compact groups, Mem. Amer. Math. Soc. 320 (1985). MR 86h:46091
  • [LM] D. Lind and B. Marcus, An Introduction to Symbolic Dynamics and Coding, Cambridge Univ. Press, Cambridge, 1995. MR 97a:58050
  • [M] B. Marcus, Factors and extensions of full shifts, Monatshefte Math. 88 (1979), 239-247. MR 81g:28023
  • [MT1] B. Marcus and S. Tuncel, The weight-per-symbol polytope and scaffolds of invariants associated with Markov chains, Ergod.Th. and Dynam. Sys. 11 (1991), 129-180. MR 92g:28038
  • [MT2] B. Marcus and S. Tuncel, Entropy at a weight-per-symbol and embeddings of Markov chains, Invent. Math. 102 (1990), 235-266. MR 91k:28023
  • [MT3] B. Marcus and S. Tuncel, Matrices of polynomials, positivity, and finite equivalence of Markov chains, J. Amer.Math. Soc. 6 (1993), 131-147. MR 93e:28022
  • [MT4] B. Marcus and S. Tuncel, On large powers of positive polynomials in several variables, preprint.
  • [MT5] B. Marcus and S. Tuncel, Resolving Markov chains onto Bernoulli shifts, preprint.
  • [O] D. Ornstein, Ergodic Theory, Randomness and Dynamical Systems, Yale Univ. Press, New Haven, 1974. MR 56:5836
  • [PS] W. Parry and K. Schmidt, Natural coefficients and invariants for Markov shifts, Invent. Math. 76 (1984), 15-32. MR 86b:28022a
  • [PT] W. Parry and S. Tuncel, On the stochastic and topological structure of Markov chains, Bull. London Math. Soc. 14 (1982), 16-27. MR 84i:28024
  • [T] S. Tuncel, Faces of Markov chains and matrices of polynomials, Contemp. Math., Vol. 135, Amer. Math. Soc., Providence, 1992, pp. 391-422. MR 94m:28034

Similar Articles

Retrieve articles in Electronic Research Announcements of the American Mathematical Society with MSC (1991): 28D20, 11C08, 05A10

Retrieve articles in all journals with MSC (1991): 28D20, 11C08, 05A10

Additional Information

Brian Marcus
Affiliation: IBM Almaden Research Center, 650 Harry Road, San Jose, CA 95120

Selim Tuncel
Affiliation: Department of Mathematics, Box 354350, University of Washington, Seattle, WA 98195

Received by editor(s): January 21, 1999
Published electronically: June 30, 1999
Additional Notes: Partially supported by NSF Grant DMS–9622866
Communicated by: Klaus Schmidt
Article copyright: © Copyright 1999 American Mathematical Society

American Mathematical Society