2013/11/15 by Takeharu Shiraga, Shiraga, Takeharu, Yukiko Yamauchi +5
Computer Science · #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #cs.DM
paper · pdf · doi:10.48550/arxiv.1311.3749
arxiv created 2015/08/11 · arxiv updated 2015/08/12
The rotor-router model is a deterministic process analogous to a simple random walk on a graph. This paper is concerned with a generalized model, functional-router model, which imitates a Markov chain possibly containing irrational transition probabilities. We investigate the discrepancy of the number of tokens at a single vertex between the functional-router model and its corresponding Markov chain, and give an upper bound in terms of the mixing time of the Markov chain.