Transience and recurrence of rotor-router walks on directed covers of graphs

Wilfried Huss (Vienna University of Technology)
Ecaterina Sava (Graz University of Technology)

Abstract


The aim of this note is to extend the result of Angel and Holroyd concerning the transience and the recurrence of transfinite rotor-router walks, for random initial configuration of rotors on homogeneous trees. We address the same question on directed covers of finite graphs, which are also called trees with finitely many cone types or periodic trees. Furthermore, we provide an example of a directed cover such that the rotor-router walk can be either recurrent or transient, depending only on the planar embedding of the periodic tree. An Erratum is available in ECP volume 19, paper 71, (2014).

Full Text: Download PDF | View PDF online (requires PDF plugin)

Pages: 1-13

Publication Date: September 22, 2012

DOI: 10.1214/ECP.v17-2096

References

  • Angel, Omer; Holroyd, Alexander E. Rotor walks on general trees. SIAM J. Discrete Math. 25 (2011), no. 1, 423--446. MR2801237
  • Bak, Per; Tang, Chao; Wiesenfeld, Kurt. Self-organized criticality. Phys. Rev. A (3) 38 (1988), no. 1, 364--374. MR0949160
  • 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, SIAM, Philadelphia, PA, 2006. MR2498151
  • Cooper, Joshua N.; Spencer, Joel. Simulating a random walk with constant error. Combin. Probab. Comput. 15 (2006), no. 6, 815--822. MR2271828
  • Doerr, Benjamin; Friedrich, Tobias. Deterministic random walks on the two-dimensional grid. Algorithms and computation, 474--483, Lecture Notes in Comput. Sci., 4288, Springer, Berlin, 2006. MR2296129
  • Giacaglia, Giuliano Pezzolo; Levine, Lionel; Propp, James; Zayas-Palmer, Linda. Local-to-global principles for the hitting sequence of a rotor walk. Electron. J. Combin. 19 (2012), no. 1, P5, 23 pp. MR2880636
  • Gilch, Lorenz A.; Müller, Sebastian. Random walks on directed covers of graphs. J. Theoret. Probab. 24 (2011), no. 1, 118--149. MR2782713
  • Harris, Theodore E. The theory of branching processes. Die Grundlehren der Mathematischen Wissenschaften, Bd. 119 Springer-Verlag, Berlin; Prentice-Hall, Inc., Englewood Cliffs, N.J. 1963 xiv+230 pp. MR0163361
  • Holroyd, Alexander E.; Propp, James. Rotor walks and Markov chains. Algorithmic probability and combinatorics, 105--126, Contemp. Math., 520, Amer. Math. Soc., Providence, RI, 2010. MR2681857
  • Huss, Wilfried; Sava, Ecaterina. Rotor-router aggregation on the comb. Electron. J. Combin. 18 (2011), no. 1, P224, 23 pp. MR2861403
  • Huss, Wilfried; Sava, Ecaterina. The rotor-router group of directed covers of graphs, Electron. J. Combin. 19 (2012), no. 3, P30.
  • Landau, Itamar; Levine, Lionel. The rotor-router model on regular trees. J. Combin. Theory Ser. A 116 (2009), no. 2, 421--433. MR2475025
  • R. Lyons and Y. Peres, Probabilty on trees and networks, preprint.
  • Lyons, Russell. Random walks and percolation on trees. Ann. Probab. 18 (1990), no. 3, 931--958. MR1062053
  • Nagnibeda, Tatiana; Woess, Wolfgang. Random walks on trees with finitely many cone types. J. Theoret. Probab. 15 (2002), no. 2, 383--422. MR1898814
  • V. B. Priezzhev, Deepak Dhar, Abhishek Dhar, and Supriya Krishnamurthy, Eulerian walkers as a model of self-organized criticality, Phys. Rev. Lett. 77 (1996), no. 25, 5079--5082.
  • Takacs, Christiane. Random walk on periodic trees. Electron. J. Probab. 2 (1997), no. 1, 1--16 (electronic). MR1436761
Bookmark and Share


Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.