Rotor walks on transient graphs and the wired spanning forest

DOI10.1137/18M1217139zbMATH Open1428.05287arXiv1809.09790WikidataQ126593393 ScholiaQ126593393MaRDI QIDQ5204068FDOQ5204068

Authors: Swee Hong Chan 

Publication date: 9 December 2019

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Abstract: We study rotor walks on transient graphs with initial rotor configuration sampled from the oriented wired uniform spanning forest (OWUSF) measure. We show that the expected number of visits to any vertex by the rotor walk is at most equal to the expected number of visits by the simple random walk. In particular, this implies that this walk is transient. When these two numbers coincide, we show that the rotor configuration at the end of the process also has the law of OWUSF. Furthermore, if the graph is vertex-transitive, we show that the average number of visits by $n$ consecutive rotor walks converges to the Green function of the simple random walk as $n$ tends to infinity. This answers a question posed by Florescu, Ganguly, Levine, and Peres (2014).

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

Recommendations

• Infinite-step stationarity of rotor walk and the wired spanning forest
• Rotor walks on general trees
• The range of a rotor walk
• Rotor-routing on Galton-Watson trees
• Transience and recurrence of rotor-router walks on directed covers of graphs

zbMATH Keywords

stationary distributionrotor walkuniform spanning forestwired spanning foresttransience and recurrencerotor router

Mathematics Subject Classification ID

Random walks, random surfaces, lattice animals, etc. in equilibrium statistical mechanics (82B41) Random walks on graphs (05C81) Dynamic lattice systems (kinetic Ising, etc.) and systems on graphs in time-dependent statistical mechanics (82C20)

Cites Work

• Self-organized critical state of sandpile automaton models
• Groups of polynomial growth and expanding maps. Appendix by Jacques Tits
• Generating random elements of finite distributive lattices
• Probability on trees and networks
• Strong spherical asymptotics for rotor-router aggregation and the divisible sandpile
• Simulating a Random Walk with Constant Error
• An elementary proof of the strong law of large numbers
• Rotor walks and Markov chains
• Chip-Firing and Rotor-Routing on Directed Graphs
• The rotor-router model on regular trees
• Choosing a spanning tree for the integer lattice uniformly
• Uniform spanning forests
• Deterministic random walks
• Recurrent rotor-router configurations
• Rotor-routing on Galton-Watson trees
• Rotor walks on general trees
• Escape rates for rotor walks in \(\mathbb{Z}^d\)
• Isoperimetric Inequalities and Decay of Iterated Kernels for Almost-transitive Markov Chains
• Sharp bounds on random walk eigenvalues via spectral embedding
• Occupation measure of random walks and wired spanning forests in balls of Cayley graphs
• Undirected and directed graphs with near polynomial growth
• Random walks with local memory
• Erratum to: ``Transience and recurrence of rotor-router walks on directed covers of graphs
• Abelian networks IV. Dynamics of nonhalting networks

Cited In (4)

• Infinite-step stationarity of rotor walk and the wired spanning forest
• Recurrence of horizontal-vertical walks
• Range and speed of rotor walks on trees
• A rotor configuration with maximum escape rate

This page was built for publication: Rotor walks on transient graphs and the wired spanning forest

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