Deterministic random walks for rapidly mixing chains

Takeharu Shiraga, Yukiko Yamauchi, Shuji Kijima, Masafumi Yamashita

Research output: Contribution to journalArticlepeer-review

3 Citations (Scopus)


The rotor-router model is a deterministic process analogous to a simple random walk on a graph, and the discrepancy of token configurations between the rotor-router model and its corresponding random walk has been investigated in some contexts. Motivated by general Markov chains beyond simple random walks, this paper investigates a generalized model which imitates a Markov chain (of multiple tokens) possibly containing irrational transition probabilities. We are concerned with the vertexwise discrepancy of the numbers of tokens between the generalized model and its corresponding Markov chain, and present an upper bound of the discrepancy in terms of the mixing time of the Markov chain.

Original languageEnglish
Pages (from-to)2180-2193
Number of pages14
JournalSIAM Journal on Discrete Mathematics
Issue number3
Publication statusPublished - 2018

All Science Journal Classification (ASJC) codes

  • General Mathematics


Dive into the research topics of 'Deterministic random walks for rapidly mixing chains'. Together they form a unique fingerprint.

Cite this