Orbits of rotor-router operation and stationary distribution of random walks on directed graphs
arXiv:1403.5875 · doi:10.1016/j.aam.2015.06.006
Abstract
The rotor-router model is a popular deterministic analogue of random walk. In this paper we prove that all orbits of the rotor-router operation have the same size on a strongly connected directed graph (digraph) and give a formula for the size. By using this formula we address the following open question about orbits of the rotor-router operation: Is there an infinite family of non-Eulerian strongly connected digraphs such that the rotor-router operation on each digraph has a single orbit? It turns out that on a strongly connected digraph the stationary distribution of the simple random walk coincides with the frequency of vertices in a rotor walk. In this common aspect a rotor walk simulates a random walk. This gives one similarity between two models on (finite) digraphs.
9 pages, 4 figures. To appear in Advances in Applied Mathematics
Cited by in corpus (6)
- Abelian networks IV. Dynamics of nonhalting networks
- Rotor-routing orbits in directed graphs and the Picard group
- Sandpile groups and the coeulerian property for random directed graphs
- Rotor-routing reachability is easy, chip-firing reachability is hard
- Perfect boundaries in rotor-router aggregation on cylinders
- Multi-Eulerian tours of directed graphs