×
Collevecchio, Andrea; Schmitz, Tom

Bounds on the speed and on regeneration times for certain processes on regular trees. (English) Zbl 1225.60156

Ann. Appl. Probab. 21, No. 3, 1073-1101 (2011).
The authors develop a technique that provides a lower bound on the speed of transient random walks in a random environment on regular trees. An auxiliary branching process is constructed to this aim. The escape probability from the root of the tree is proved to be bounded from below by the survival probability of the branching process. This result and an upper bound for the expected number of returns to the root provide a lower bound on the speed. A refinement of this technique yields upper bounds on the first generation level and regeneration time. In particular, a lower and upper bound on the covariance in the annealed invariance principle follows. These methods are general and also apply in the case of once-reinforced random walks. R. Durrett, H. Kesten and V. Limic [Probab. Theory Relat. Fields 122, No. 4, 567–592 (2002; Zbl 0995.60042)] proved an upper bound of the form \(b/(b+\delta)\) for the speed on the \(b\)-ary tree, where \(\delta\) is the reinforcement parameter. For \(\delta>1\), the authors provide a lower bound of the form \(\gamma^2b/(b+\delta)\), where \(\gamma\) is the survival probability of the associated branching process.
Reviewer: Dominique Lepingle (Orléans)

Cited in 2 Documents

MSC:

60K37 Processes in random environments
60K99 Special processes

Keywords:

random walk in a random environment; once edge-reinforced random walk; lower bound on the speed; regeneration times; regular trees

Citations:

Zbl 0995.60042
Cite Review PDF
Full Text: DOI arXiv

References:

[1] Aidékon, E. (2008). Transient random walks in random environment on a Galton-Watson tree. Probab. Theory Related Fields 142 525-559. · Zbl 1146.60078 · doi:10.1007/s00440-007-0114-x
[2] Aidékon, E. (2010). Large deviations for transient random walks in random environment on a Galton-Watson tree. Ann. Inst. H. Poincaré Probab. Statist. 46 159-189. · Zbl 1191.60119 · doi:10.1214/09-AIHP204
[3] Aidékon, E. (2009). Marches aléatoires en milieu aléatoire et marches branchantes. Ph.D. thesis, Univ. Paris VI. Available at .
[4] Chen, D. (2002). Estimating the speed of random walks. In Applied Probability ( Hong Kong , 1999). AMS/IP Stud. Adv. Math. 26 17-23. Amer. Math. Soc., Providence, RI. · Zbl 1007.60038
[5] Collevecchio, A. (2006). Limit theorems for reinforced random walks on certain trees. Probab. Theory Related Fields 136 81-101. · Zbl 1109.60027 · doi:10.1007/s00440-005-0476-x
[6] Collevecchio, A. (2006). On the transience of processes defined on Galton-Watson trees. Ann. Probab. 34 870-878. · Zbl 1104.60048 · doi:10.1214/009117905000000837
[7] Collevecchio, A. (2009). Limit theorems for vertex-reinforced jump processes on regular trees. Electron. J. Probab. 14 1936-1962. · Zbl 1189.60170
[8] Dai, J. J. (2005). A once edge-reinforced random walk on a Galton-Watson tree is transient. Statist. Probab. Lett. 73 115-124. · Zbl 1078.60033 · doi:10.1016/j.spl.2005.03.001
[9] Davis, B. (1990). Reinforced random walk. Probab. Theory Related Fields 84 203-229. · Zbl 0665.60077 · doi:10.1007/BF01197845
[10] Davis, B. and Volkov, S. (2002). Continuous time vertex-reinforced jump processes. Probab. Theory Related Fields 123 281-300. · Zbl 1009.60027 · doi:10.1007/s004400100189
[11] Dembo, A., Gantert, N., Peres, Y. and Zeitouni, O. (2002). Large deviations for random walks on Galton-Watson trees: Averaging and uncertainty. Probab. Theory Related Fields 122 241-288. · Zbl 0996.60110 · doi:10.1007/s004400100162
[12] Durrett, R. (1996). Probability : Theory and Examples , 2nd ed. Duxbury Press, Belmont, CA. · Zbl 1202.60001
[13] Durrett, R., Kesten, H. and Limic, V. (2002). Once edge-reinforced random walk on a tree. Probab. Theory Related Fields 122 567-592. · Zbl 0995.60042 · doi:10.1007/s004400100179
[14] Gross, T. (2004). Marche aléatoire en milieu aléatoire sur un arbre. Ph.D. thesis, Univ. Paris VI.
[15] Hu, Y. and Shi, Z. (2007). Slow movement of random walk in random environment on a regular tree. Ann. Probab. 35 1978-1997. · Zbl 1124.60083 · doi:10.1214/009117906000001150
[16] Hu, Y. and Shi, Z. (2007). A subdiffusive behaviour of recurrent random walk in random environment on a regular tree. Probab. Theory Related Fields 138 521-549. · Zbl 1113.60096 · doi:10.1007/s00440-006-0036-z
[17] Lyons, R. and Pemantle, R. (1992). Random walk in a random environment and first-passage percolation on trees. Ann. Probab. 20 125-136. · Zbl 0766.60091 · doi:10.1214/aop/1176989540
[18] Lyons, R., Pemantle, R. and Peres, Y. (1996). Biased random walks on Galton-Watson trees. Probab. Theory Related Fields 106 249-264. · Zbl 0859.60076 · doi:10.1007/s004400050064
[19] Menshikov, M. and Petritis, D. (2002). On random walks in random environment on trees and their relationship with multiplicative chaos. In Mathematics and Computer Science , II ( Versailles , 2002) 415-422. Birkhäuser, Basel. · Zbl 1027.60101
[20] Pemantle, R. (2007). A survey of random processes with reinforcement. Probab. Surv. 4 1-79 (electronic). · Zbl 1189.60138 · doi:10.1214/07-PS094
[21] Peres, Y. and Zeitouni, O. (2008). A central limit theorem for biased random walks on Galton-Watson trees. Probab. Theory Related Fields 140 595-629. · Zbl 1141.60073 · doi:10.1007/s00440-007-0077-y
[22] Sellke, T. (1994). Reinforced random walk on the d-dimensional integer lattice. Technical Report 94-26, Dept. Statistics, Purdue Univ. · Zbl 1154.82011
[23] Shen, L. (2003). On ballistic diffusions in random environment. Ann. Inst. H. Poincaré Probab. Statist. 39 839-876. · Zbl 1026.60096 · doi:10.1016/S0246-0203(03)00027-X
[24] Sznitman, A.-S. (2004). Topics in random walks in random environment. In School and Conference on Probability Theory. ICTP Lect. Notes , XVII 203-266 (electronic). Abdus Salam Int. Cent. Theoret. Phys., Trieste. Available at . · Zbl 1060.60102
[25] Virág, B. (2000). On the speed of random walks on graphs. Ann. Probab. 28 379-394. · Zbl 1044.60034 · doi:10.1214/aop/1019160123
[26] Zeitouni, O. (2004). Random walks in random environment. In Lectures on Probability Theory and Statistics. Lecture Notes in Math. 1837 189-312. Springer, Berlin. · Zbl 1060.60103
[27] Zeitouni, O. (2006). Random walks in random environments. J. Phys. A 39 R433-R464. · Zbl 1108.60085 · doi:10.1088/0305-4470/39/40/R01
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.