Rotor Walks and Markov Chains

By Alexander E. Holroyd, James Gary Propp. 2009

82 citations recorded by the source corpus.

The rotor walk is a derandomized version of the random walk on a graph. On successive visits to any given vertex, the walker is routed to each of the neighboring vertices in some fixed cyclic order, rather than to a random sequence of neighbors. The concept generalizes naturally to Markov chains on a countable state space. Subject to general conditions, we prove that many natural quantities associated with the rotor walk (including normalized hitting frequencies, hitting times and occupation frequencies) concentrate around their expected values for the random walk. Furthermore, the concentration is stronger than that associated with repeated runs of the random walk, with discrepancy at most C/n after n runs (for an explicit constant C), rather than c/sqrt n.

Subfields: Condensed Matter Physics, Mathematical Physics, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/47d5c1f93b3e892b3fff95ba12ff5e4567677577

Citations in the corpus

• Combinatorial, piecewise-linear, and birational homomesy for products of two chains (2013, unknown): “The notion of looking at the average of a quantity over an orbit was an outgrowth of the second author’s work on chip-firing and rotor-routing [8, 9]; see in particular Proposition 3 of [13].”