| Autor: |
TAKEHARU SHIRAGA, YUKIKO YAMAUCHI, SHUJI KIJIMA, MASAFUMI YAMASHITA |
| Předmět: |
|
| Zdroj: |
SIAM Journal on Discrete Mathematics; 2018, Vol. 32 Issue 3, p2180-2193, 14p |
| Abstrakt: |
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. [ABSTRACT FROM AUTHOR] |
| Databáze: |
Complementary Index |
| Externí odkaz: |
|
