Rotor walks on transient graphs and the wired spanning forest

DOI10.1137/18M1217139MaRDI QIDQ5204068zbMATH OpenWikidataFDO

Authors Swee Hong Chan

Publication date 9 December 2019

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

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

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)

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).

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

Cites work

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

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)