Random walk in a finite directed graph subject to a synchronizing road coloring

Abstract

A constructive proof is given to the fact that any ergodic Markov chain can be realized as a random walk subject to a synchronizing road coloring. Redundancy (ratio of extra entropy) in such a realization is also studied.

References in corpus (1)

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