Orbits of rotor-router operation and stationary distribution of random walks on directed graphs

DOI10.1016/J.AAM.2015.06.006MaRDI QIDQ494127zbMATH OpenOpenAlexFDO

Authors Trung Van Pham

Publication date 31 August 2015

Published in Advances in Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1403.5875

zbMATH Keywords

Eulerian Walkeroriented spanning treerandom walkrecurrent staterotor-router modelspanning treestationary distribution

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Eulerian and Hamiltonian graphs (05C45) Games on graphs (graph-theoretic aspects) (05C57) Random walks on graphs (05C81)

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.

Recommendations

• Deterministic random walks on finite graphs
• Deterministic random walks on finite graphs
• The range of a rotor walk
• The rotor-router group of directed covers of graphs
• The rotor-router model on regular trees

Cites work

• A proof of the Markov chain tree theorem
• Chip-Firing and Rotor-Routing on Directed Graphs
• Deterministic random walks
• Deterministic random walks on the two-dimensional grid
• scientific article; zbMATH DE number 1268810 (Why is no real title available?)
• Rotor walks and Markov chains
• Simulating a Random Walk with Constant Error

Cited in

(10)

• Algorithmic aspects of rotor-routing and the notion of linear equivalence
• Rotor-routing reachability is easy, chip-firing reachability is hard
• Random integral matrices: universality of surjectivity and the cokernel
• Sandpile groups and the coeulerian property for random directed graphs
• CoEulerian graphs
• Multi-Eulerian tours of directed graphs
• Coalescing walks on rotor-router systems
• The rotor-router group of directed covers of graphs
• Abelian networks IV. Dynamics of nonhalting networks
• Perfect boundaries in rotor-router aggregation on cylinders

This page was built for publication: Orbits of rotor-router operation and stationary distribution of random walks on directed graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q494127)