Recurrence and transience of a multi-excited random walk on a regular tree

Anne-Laure Basdevant (University Toulouse III)
Arvind Singh (Zurich University)


We study a model of multi-excited random walk on a regular tree which generalizes the models of the once excited random walk and the digging random walk introduced by Volkov (2003). We show the existence of a phase transition and provide a criterion for the recurrence/transience property of the walk. In particular, we prove that the asymptotic behaviour of the walk depends on the order of the excitations, which contrasts with the one dimensional setting studied by Zerner (2005). We also consider the limiting speed of the walk in the transient regime and conjecture that it is not a monotonic function of the environment.

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

Pages: 1628-1669

Publication Date: July 9, 2009

DOI: 10.1214/EJP.v14-672


  1. Amir, G.; Benjamini, I. Kozma, G. Excited random walk against a wall. Probab. Theory Related Fields 140 (2008), no. 1-2, 83--102. MR2357671
  2. Antal, T.; Redner, S. The excited random walk in one dimension. J. Phys. A 38 (2005), no. 12, 2555--2577. MR2132073
  3. Athreya, K. B.; Ney, P. E. Branching processes. Die Grundlehren der mathematischen Wissenschaften, Band 196. Springer-Verlag, New York-Heidelberg, 1972. xi+287 pp. MR0373040
  4. Basdevant, A.-L.; Singh, A.. On the speed of a cookie random walk. Probab. Theory Related Fields 141 (2008), no. 3-4, 625--645. MR2391167
  5. Basdevant, A.-L.; Singh, A.. Rate of growth of a transient cookie random walk. Electron. J. Probab. 13 (2008), no. 26, 811--851. MR2399297
  6. Benjamini, I.; Wilson, D. B. Excited random walk. Electron. Comm. Probab. 8 (2003), 86--92 (electronic). MR1987097
  7. Bérard, J.; Ramírez, A.. Central limit theorem for the excited random walk in dimension D≥2. Electron. Comm. Probab. 12 (2007), 303--314 (electronic). MR2342709
  8. Bertoin, J.. Lévy processes. Cambridge Tracts in Mathematics, 121. Cambridge University Press, Cambridge, 1996. x+265 pp. ISBN: 0-521-56243-0 MR1406564
  9. Chi, Z.. Limit laws of estimators for critical multi-type Galton-Watson processes. Ann. Appl. Probab. 14 (2004), no. 4, 1992--2015. MR2099660
  10. Harris, Th. 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
  11. Kosygina, E.; Zerner, M. P. W. Positively and negatively excited random walks on integers, with branching processes. Electron. J. Probab. 13 (2008), no. 64, 1952--1979. MR2453552
  12. Kozma, G. Excited random walk in three dimensions has positive speed. Preprint (2003), math.PR/0310305
  13. Kozma, G. Excited random walk in two dimensions has linear speed. Preprint (2005), math.PR/0512535
  14. Lyons, R.; Pemantle, R.; Peres, Y.. Biased random walks on Galton-Watson trees. Probab. Theory Related Fields 106 (1996), no. 2, 249--264. MR1410689
  15. Lyons, R.; Pemantle, R.; Peres, Y.. Unsolved problems concerning random walks on trees. Classical and modern branching processes (Minneapolis, MN, 1994), 223--237, IMA Vol. Math. Appl., 84, Springer, New York, 1997. MR1601753
  16. Menshikov, M. V.; Volkov, S. E. Branching Markov chains: qualitative characteristics. Markov Process. Related Fields 3 (1997), no. 2, 225--241. MR1468175
  17. Mountford, T.; Pimentel, L. P. R.; Valle, G.. On the speed of the one-dimensional excited random walk in the transient regime. ALEA Lat. Am. J. Probab. Math. Stat. 2 (2006), 279--296 (electronic). MR2285733
  18. Müller, S.. Recurrence for branching Markov chains. Electron. Commun. Probab. 13 (2008), 576--605. MR2461533
  19. Seneta, E. Nonnegative matrices and Markov chains. Second edition. Springer Series in Statistics. Springer-Verlag, New York, 1981. xiii+279 pp. ISBN: 0-387-90598-7 MR0719544
  20. Seneta, E.; Vere-Jones, D. On quasi-stationary distributions in discrete-time Markov chains with a denumerable infinity of states. J. Appl. Probability 3 1966 403--434. MR0207047
  21. van der Hofstad, R.; Holmes, M. An expansion for self-interacting random walks. Preprint (2007), abs/0706.0614v3
  22. van der Hofstad, R.; Holmes, M. Monotonicity for excited random walk in high dimensions. To appear in Probab. Theory Related Fields (2009), abs/0803.1881
  23. Vere-Jones, D. Ergodic properties of nonnegative matrices. I. Pacific J. Math. 22 1967 361--386. MR0214145
  24. Volkov, S.. Excited random walk on trees. Electron. J. Probab. 8 (2003), no. 23, 15 pp. (electronic). MR2041824
  25. Zerner, M. P. W. Multi-excited random walks on integers. Probab. Theory Related Fields 133 (2005), no. 1, 98--122. MR2197139
  26. Zerner, M. P. W. Recurrence and transience of excited random walks on Zd and strips. Electron. Comm. Probab. 11 (2006), 118--128 (electronic). MR2231739

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