Deterministic random walks on finite graphs |
| |
Authors: | Shuji Kijima Kentaro Koga Kazuhisa Makino |
| |
Affiliation: | 1. Graduate School of Information Science and Electrical Engineering, Kyushu University, Fukuoka 819‐0395, Japan;2. FANUC Ltd., Yamanashi, Japan;3. Research Institute for Mathematical Sciences, Kyoto University, Kyoto 606‐8502, Japan |
| |
Abstract: | The rotor‐router model, also known as the Propp machine, is a deterministic process analogous to a random walk on a graph. Instead of distributing tokens to randomly chosen neighbors, the Propp machine deterministically serves the neighbors in a fixed order by associating to each vertex a “rotor‐router” pointing to one of its neighbors. This paper investigates the discrepancy at a single vertex between the number of tokens in the rotor‐router model and the expected number of tokens in a random walk, for finite graphs in general. We show that the discrepancy is bounded by O (mn) at any time for any initial configuration if the corresponding random walk is lazy and reversible, where n and m denote the numbers of nodes and edges, respectively. For a lower bound, we show examples of graphs and initial configurations for which the discrepancy at a single vertex is Ω(m) at any time (> 0). For some special graphs, namely hypercube skeletons and Johnson graphs, we give a polylogarithmic upper bound, in terms of the number of nodes, for the discrepancy. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 46,739–761, 2015 |
| |
Keywords: | rotor‐router model Propp machine derandomization random walk Markov chain |
|
|