Deterministic random walks on finite graphs12. Issue 4 (20th March 2014)

• Record Type: Journal Article
• Authors: Kijima, Shuji; Koga, Kentaro; Makino, Kazuhisa
• Is Part Of: Random structures & algorithms. Volume 46:Issue 4(2015)
• Page Start: 739
• Page End: 761
• Publication Date: 2014-03-20
• Subjects: Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20533
• Languages: English
• ISSNs: 1042-9832

Abstract

<abstract abstract-type="main"> <title>ABSTRACT</title> <p>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 (&gt; 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</p> </abstract>