Article contents
Realization of an Ergodic Markov Chain as a Random Walk Subject to a Synchronizing Road Coloring
Published online by Cambridge University Press: 14 July 2016
Abstract
An ergodic Markov chain is proved to be the realization of a random walk in a directed graph subject to a synchronizing road coloring. The result ensures the existence of appropriate random mappings in Propp-Wilson's coupling from the past. The proof is based on the road coloring theorem. A necessary and sufficient condition for approximate preservation of entropies is also given.
Keywords
- Type
- Research Papers
- Information
- Copyright
- Copyright © Applied Probability Trust 2011
Footnotes
Research supported by KAKENHI (20740060).
References
- 3
- Cited by