Realization of finite-state mixing Markov chain as a random walk subject to a synchronizing road coloring

preprint2010arXivOpen access

Abstract

A mixing Markov chain is proved to be realized as a random walk in a directed graph subject to a synchronizing road coloring. The result ensures 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.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.