×

Infinite-step stationarity of rotor walk and the wired spanning forest. (English) Zbl 1462.05327

Summary: 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 [SIAM J. Discrete Math. 33, No. 4, 2369–2393 (2019; Zbl 1428.05287)].

MSC:

05C81 Random walks on graphs
82C20 Dynamic lattice systems (kinetic Ising, etc.) and systems on graphs in time-dependent statistical mechanics
05C05 Trees

Citations:

Zbl 1428.05287
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Angel, Omer; Holroyd, Alexander E., Rotor walks on general trees, SIAM J. Discrete Math., 25, 1, 423-446 (2011) · Zbl 1252.05032 · doi:10.1137/100814299
[2] Angel, Omer; Holroyd, Alexander E., Recurrent rotor-router configurations, J. Comb., 3, 2, 185-194 (2012) · Zbl 1264.82067 · doi:10.4310/JOC.2012.v3.n2.a3
[3] Aldous, David J., The random walk construction of uniform spanning trees and uniform labelled trees, SIAM J. Discrete Math., 3, 4, 450-465 (1990) · Zbl 0717.05028 · doi:10.1137/0403039
[4] Bond, Benjamin; Levine, Lionel, Abelian networks I. Foundations and examples, SIAM J. Discrete Math., 30, 2, 856-874 (2016) · Zbl 1356.68072 · doi:10.1137/15M1030984
[5] Benjamini, Itai; Lyons, Russell; Peres, Yuval; Schramm, Oded, Uniform spanning forests, Ann. Probab., 29, 1, 1-65 (2001) · Zbl 1016.60009 · doi:10.1214/aop/1008956321
[6] A. Broder, Generating random spanning trees, in Proc. 30th SFCS, IEEE Comp. Soc., Washington, DC (1989), 442-447.
[7] Bak, Per; Tang, Chao; Wiesenfeld, Kurt, Self-organized criticality, Phys. Rev. A (3), 38, 1, 364-374 (1988) · Zbl 1230.37103 · doi:10.1103/PhysRevA.38.364
[8] Cooper, Joshua; Doerr, Benjamin; Spencer, Joel; Tardos, Garbor, Deterministic random walks. Proceedings of the Eighth Workshop on Algorithm Engineering and Experiments and the Third Workshop on Analytic Algorithmics and Combinatorics, 185-197 (2006), SIAM, Philadelphia, PA · Zbl 1423.05158
[9] S. H. Chan, L. Greco, L. Levine, and P. Li, Random walks with local memory, preprint (2018), 29 pp., 1809.04710.
[10] Chan, Swee Hong, Rotor walks on transient graphs and the wired spanning forest, SIAM J. Discrete Math., 33, 4, 2369-2393 (2019) · Zbl 1428.05287 · doi:10.1137/18M1217139
[11] Chan, Swee Hong, A rotor configuration with maximum escape rate, Electron. Commun. Probab., 25, Paper No. 19, 5 pp. (2020) · Zbl 1440.05183 · doi:10.1214/20-ecp298
[12] Cooper, Joshua N.; Spencer, Joel, Simulating a random walk with constant error, Combin. Probab. Comput., 15, 6, 815-822 (2006) · Zbl 1113.60047 · doi:10.1017/S0963548306007565
[13] Doerr, Benjamin; Friedrich, Tobias, Deterministic random walks on the two-dimensional grid, Combin. Probab. Comput., 18, 1-2, 123-144 (2009) · Zbl 1185.05130 · doi:10.1017/S0963548308009589
[14] Dumitriu, Ioana; Tetali, Prasad; Winkler, Peter, On playing golf with two balls, SIAM J. Discrete Math., 16, 4, 604-615 (2003) · Zbl 1032.60065 · doi:10.1137/S0895480102408341
[15] Florescu, Laura; Ganguly, Shirshendu; Levine, Lionel; Peres, Yuval, Escape rates for rotor walks in \(\mathbb{Z}^d\), SIAM J. Discrete Math., 28, 1, 323-334 (2014) · Zbl 1292.05236 · doi:10.1137/130908646
[16] Florescu, Laura; Levine, Lionel; Peres, Yuval, The range of a rotor walk, Amer. Math. Monthly, 123, 7, 627-642 (2016) · Zbl 1391.60019 · doi:10.4169/amer.math.monthly.123.7.627
[17] D. He, A rotor configuration in \(\mathbbZ^d\) where Schramm’s bound of escape rates attains, preprint (2014), 20 pp., 1405.3400.
[18] Holroyd, Alexander E.; Levine, Lionel; M\'{e}sz\'{a}ros, Karola; Peres, Yuval; Propp, James; Wilson, David B., Chip-firing and rotor-routing on directed graphs. In and out of equilibrium. 2, Progr. Probab. 60, 331-364 (2008), Birkh\"{a}user, Basel · Zbl 1173.82339 · doi:10.1007/978-3-7643-8786-0\_17
[19] Huss, Wilfried; M\"{u}ller, Sebastian; Sava-Huss, Ecaterina, Rotor-routing on Galton-Watson trees, Electron. Commun. Probab., 20, no. 49, 12 pp. (2015) · Zbl 1321.60177 · doi:10.1214/ECP.v20-4000
[20] Holroyd, Alexander E.; Propp, James, Rotor walks and Markov chains. Algorithmic probability and combinatorics, Contemp. Math. 520, 105-126 (2010), Amer. Math. Soc., Providence, RI · Zbl 1217.82042 · doi:10.1090/conm/520/10256
[21] 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. · Zbl 1457.60132
[22] Huss, Wilfried; Sava-Huss, Ecaterina, Range and speed of rotor walks on trees, J. Theoret. Probab., 33, 3, 1657-1690 (2020) · Zbl 1444.05133 · doi:10.1007/s10959-019-00904-1
[23] Hutchcroft, Tom, Interlacements and the wired uniform spanning forest, Ann. Probab., 46, 2, 1170-1200 (2018) · Zbl 1391.60021 · doi:10.1214/17-AOP1203
[24] J\'{a}rai, Antal A.; Redig, Frank, Infinite volume limit of the abelian sandpile model in dimensions \(d\geq3\), Probab. Theory Related Fields, 141, 1-2, 181-212 (2008) · Zbl 1135.60342 · doi:10.1007/s00440-007-0083-0
[25] Lawler, Gregory F., A self-avoiding random walk, Duke Math. J., 47, 3, 655-693 (1980) · Zbl 0445.60058
[26] Landau, Itamar; Levine, Lionel, The rotor-router model on regular trees, J. Combin. Theory Ser. A, 116, 2, 421-433 (2009) · Zbl 1179.05031 · doi:10.1016/j.jcta.2008.05.012
[27] Lyons, Russell; Morris, Benjamin J.; Schramm, Oded, Ends in uniform spanning forests, Electron. J. Probab., 13, no. 58, 1702-1725 (2008) · Zbl 1191.60016 · doi:10.1214/EJP.v13-566
[28] Levine, Lionel; Peres, Yuval, Spherical asymptotics for the rotor-router model in \(\mathbb{Z}^d\), Indiana Univ. Math. J., 57, 1, 431-449 (2008) · Zbl 1139.60347 · doi:10.1512/iumj.2008.57.3022
[29] Levine, Lionel; Peres, Yuval, Strong spherical asymptotics for rotor-router aggregation and the divisible sandpile, Potential Anal., 30, 1, 1-27 (2009) · Zbl 1165.82309 · doi:10.1007/s11118-008-9104-6
[30] Lyons, Russell; Peres, Yuval, Probability on trees and networks, Cambridge Series in Statistical and Probabilistic Mathematics 42, xv+699 pp. (2016), Cambridge University Press, New York · Zbl 1376.05002 · doi:10.1017/9781316672815
[31] 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.
[32] Pemantle, Robin, Choosing a spanning tree for the integer lattice uniformly, Ann. Probab., 19, 4, 1559-1574 (1991) · Zbl 0758.60010
[33] J. Propp, Random walk and random aggregation, derandomized, online lecture (2003), https://www.microsoft.com/en-us/research/video/random-walk-and-random-aggregation-derandomized/Link.
[34] 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.
[35] Wilson, David Bruce, 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, 296-303 (1996), ACM, New York · Zbl 0946.60070 · doi:10.1145/237814.237880
[36] Wagner, Israel A.; Lindenbaum, Michael; Bruckstein, Alfred M., Smell as a computational resource-a lesson we can learn from the ant. Israel Symposium on Theory of Computing and Systems, Jerusalem, 1996, 219-230 (1996), IEEE Comput. Soc. Press, Los Alamitos, CA
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.