## Infinite-step stationarity of rotor walk and the wired spanning forest

HTML articles powered by AMS MathViewer

- by Swee Hong Chan PDF
- Proc. Amer. Math. Soc.
**149**(2021), 2415-2428 Request permission

## Abstract:

We study rotor walk, a deterministic counterpart of the simple random walk, on infinite transient graphs. We show that the final rotor configuration of the rotor walk (after the walker escapes to infinity) follows the law of the wired uniform spanning forest oriented toward infinity (OWUSF) measure when the initial rotor configuration is sampled from OWUSF. This result holds for all graphs for which each tree in the wired spanning forest has one single end almost surely. This answers a question posed in a previous work of the author (Chan 2018).## References

- Omer Angel and Alexander E. Holroyd,
*Rotor walks on general trees*, SIAM J. Discrete Math.**25**(2011), no. 1, 423–446. MR**2801237**, DOI 10.1137/100814299 - Omer Angel and Alexander E. Holroyd,
*Recurrent rotor-router configurations*, J. Comb.**3**(2012), no. 2, 185–194. MR**2980749**, DOI 10.4310/JOC.2012.v3.n2.a3 - David J. Aldous,
*The random walk construction of uniform spanning trees and uniform labelled trees*, SIAM J. Discrete Math.**3**(1990), no. 4, 450–465. MR**1069105**, DOI 10.1137/0403039 - Benjamin Bond and Lionel Levine,
*Abelian networks I. Foundations and examples*, SIAM J. Discrete Math.**30**(2016), no. 2, 856–874. MR**3493110**, DOI 10.1137/15M1030984 - Itai Benjamini, Russell Lyons, Yuval Peres, and Oded Schramm,
*Uniform spanning forests*, Ann. Probab.**29**(2001), no. 1, 1–65. MR**1825141**, DOI 10.1214/aop/1008956321 - A. Broder,
*Generating random spanning trees*, in Proc. 30th SFCS, IEEE Comp. Soc., Washington, DC (1989), 442–447. - Per Bak, Chao Tang, and Kurt Wiesenfeld,
*Self-organized criticality*, Phys. Rev. A (3)**38**(1988), no. 1, 364–374. MR**949160**, DOI 10.1103/PhysRevA.38.364 - Joshua Cooper, Benjamin Doerr, Joel Spencer, and Garbor Tardos,
*Deterministic random walks*, Proceedings of the Eighth Workshop on Algorithm Engineering and Experiments and the Third Workshop on Analytic Algorithmics and Combinatorics, SIAM, Philadelphia, PA, 2006, pp. 185–197. MR**2498151** - S. H. Chan, L. Greco, L. Levine, and P. Li,
*Random walks with local memory*, preprint (2018), 29 pp., arXiv:1809.04710. - Swee Hong Chan,
*Rotor walks on transient graphs and the wired spanning forest*, SIAM J. Discrete Math.**33**(2019), no. 4, 2369–2393. MR**4039517**, DOI 10.1137/18M1217139 - Swee Hong Chan,
*A rotor configuration with maximum escape rate*, Electron. Commun. Probab.**25**(2020), Paper No. 19, 5. MR**4069739**, DOI 10.1214/20-ecp298 - Joshua N. Cooper and Joel Spencer,
*Simulating a random walk with constant error*, Combin. Probab. Comput.**15**(2006), no. 6, 815–822. MR**2271828**, DOI 10.1017/S0963548306007565 - Benjamin Doerr and Tobias Friedrich,
*Deterministic random walks on the two-dimensional grid*, Combin. Probab. Comput.**18**(2009), no. 1-2, 123–144. MR**2497377**, DOI 10.1017/S0963548308009589 - Ioana Dumitriu, Prasad Tetali, and Peter Winkler,
*On playing golf with two balls*, SIAM J. Discrete Math.**16**(2003), no. 4, 604–615. MR**2032083**, DOI 10.1137/S0895480102408341 - Laura Florescu, Shirshendu Ganguly, Lionel Levine, and Yuval Peres,
*Escape rates for rotor walks in $\Bbb {Z}^d$*, SIAM J. Discrete Math.**28**(2014), no. 1, 323–334. MR**3168611**, DOI 10.1137/130908646 - Laura Florescu, Lionel Levine, and Yuval Peres,
*The range of a rotor walk*, Amer. Math. Monthly**123**(2016), no. 7, 627–642. MR**3539850**, DOI 10.4169/amer.math.monthly.123.7.627 - D. He,
*A rotor configuration in $\mathbb {Z}^d$ where Schramm’s bound of escape rates attains*, preprint (2014), 20 pp., arXiv:1405.3400. - Alexander E. Holroyd, Lionel Levine, Karola Mészáros, Yuval Peres, James Propp, and David B. Wilson,
*Chip-firing and rotor-routing on directed graphs*, In and out of equilibrium. 2, Progr. Probab., vol. 60, Birkhäuser, Basel, 2008, pp. 331–364. MR**2477390**, DOI 10.1007/978-3-7643-8786-0_{1}7 - Wilfried Huss, Sebastian Müller, and Ecaterina Sava-Huss,
*Rotor-routing on Galton-Watson trees*, Electron. Commun. Probab.**20**(2015), no. 49, 12. MR**3367899**, DOI 10.1214/ECP.v20-4000 - Alexander E. Holroyd and James Propp,
*Rotor walks and Markov chains*, Algorithmic probability and combinatorics, Contemp. Math., vol. 520, Amer. Math. Soc., Providence, RI, 2010, pp. 105–126. MR**2681857**, DOI 10.1090/conm/520/10256 - W. Huss and E. Sava-Huss, A law of large numbers for the range of rotor walks on periodic trees,
*Markov Process. Relat. Fields***26**(2020), 467–485. - Wilfried Huss and Ecaterina Sava-Huss,
*Range and speed of rotor walks on trees*, J. Theoret. Probab.**33**(2020), no. 3, 1657–1690. MR**4125970**, DOI 10.1007/s10959-019-00904-1 - Tom Hutchcroft,
*Interlacements and the wired uniform spanning forest*, Ann. Probab.**46**(2018), no. 2, 1170–1200. MR**3773383**, DOI 10.1214/17-AOP1203 - Antal A. Járai and Frank Redig,
*Infinite volume limit of the abelian sandpile model in dimensions $d\geq 3$*, Probab. Theory Related Fields**141**(2008), no. 1-2, 181–212. MR**2372969**, DOI 10.1007/s00440-007-0083-0 - Gregory F. Lawler,
*A self-avoiding random walk*, Duke Math. J.**47**(1980), no. 3, 655–693. MR**587173** - Itamar Landau and Lionel Levine,
*The rotor-router model on regular trees*, J. Combin. Theory Ser. A**116**(2009), no. 2, 421–433. MR**2475025**, DOI 10.1016/j.jcta.2008.05.012 - Russell Lyons, Benjamin J. Morris, and Oded Schramm,
*Ends in uniform spanning forests*, Electron. J. Probab.**13**(2008), no. 58, 1702–1725. MR**2448128**, DOI 10.1214/EJP.v13-566 - Lionel Levine and Yuval Peres,
*Spherical asymptotics for the rotor-router model in $\Bbb Z^d$*, Indiana Univ. Math. J.**57**(2008), no. 1, 431–449. MR**2400263**, DOI 10.1512/iumj.2008.57.3022 - Lionel Levine and Yuval Peres,
*Strong spherical asymptotics for rotor-router aggregation and the divisible sandpile*, Potential Anal.**30**(2009), no. 1, 1–27. MR**2465710**, DOI 10.1007/s11118-008-9104-6 - Russell Lyons and Yuval Peres,
*Probability on trees and networks*, Cambridge Series in Statistical and Probabilistic Mathematics, vol. 42, Cambridge University Press, New York, 2016. MR**3616205**, DOI 10.1017/9781316672815 - V. Priezzhev, D. Dhar, A. Dhar, and S. Krishnamurthy,
*Eulerian walkers as a model of self-organized criticality*, Phys. Rev. Lett.**77**(1996), 5079–5082. - Robin Pemantle,
*Choosing a spanning tree for the integer lattice uniformly*, Ann. Probab.**19**(1991), no. 4, 1559–1574. MR**1127715** - J. Propp,
*Random walk and random aggregation, derandomized*, online lecture (2003), Link. - Y. Rabani, A. Sinclair, and R. Wanka,
*Local Divergence of Markov Chains and the Analysis of Iterative Load-Balancing Schemes*, in Proc. 39th FOCS, IEEE Comp. Soc., Washington, DC (1998), 694–708. - David Bruce Wilson,
*Generating random spanning trees more quickly than the cover time*, Proceedings of the Twenty-eighth Annual ACM Symposium on the Theory of Computing (Philadelphia, PA, 1996) ACM, New York, 1996, pp. 296–303. MR**1427525**, DOI 10.1145/237814.237880 - Israel A. Wagner, Michael Lindenbaum, and Alfred M. Bruckstein,
*Smell as a computational resource—a lesson we can learn from the ant*, Israel Symposium on Theory of Computing and Systems (Jerusalem, 1996) IEEE Comput. Soc. Press, Los Alamitos, CA, 1996, pp. 219–230. MR**1436463**

## Additional Information

**Swee Hong Chan**- Affiliation: Department of Mathematics, UCLA, Los Angeles, California 90095
- MR Author ID: 1058757
- ORCID: 0000-0003-0599-9901
- Email: sweehong@math.ucla.edu
- Received by editor(s): January 6, 2020
- Received by editor(s) in revised form: November 20, 2020
- Published electronically: March 26, 2021
- Additional Notes: The author was supported in part by NSF grant DMS-1455272.
- Communicated by: David Levin
- © Copyright 2021 American Mathematical Society
- Journal: Proc. Amer. Math. Soc.
**149**(2021), 2415-2428 - MSC (2020): Primary 05C81, 82C20; Secondary 05C05
- DOI: https://doi.org/10.1090/proc/15476
- MathSciNet review: 4246794