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

Chan, Swee Hong

doi:10.1090/proc/15476

Infinite-step stationarity of rotor walk and the wired spanning forest
HTML articles powered by AMS MathViewer

by Swee Hong Chan

Proc. Amer. Math. Soc. 149 (2021), 2415-2428

DOI: https://doi.org/10.1090/proc/15476

Published electronically: March 26, 2021

PDF | 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