Almost sure convergence for stochastically biased random walks on trees. (English) Zbl 1257.05162
Summary: We are interested in the biased random walk on a supercritical Galton-Watson tree in the sense of R. Lyons [Ann. Probab. 18, No.3, 931–958 (1990; Zbl 0714.60089)] and R. Lyons, R. Pemantle and Y. Peres [Probab. Theory Relat. Fields 106, No. 2, 249–264 (1996; Zbl 0859.60076)], and study a phenomenon of slow movement. In order to observe such a slow movement, the bias needs to be random; the resulting random walk is then a tree-valued random walk in random environment. We investigate the recurrent case, and prove, under suitable general integrability assumptions, that upon the system’s non-extinction, the maximal displacement of the walk in the first \(n\) steps, divided by \((\log n)^{3}\), converges almost surely to a known positive constant.
MSC:
| 05C81 | Random walks on graphs |
| 60J80 | Branching processes (Galton-Watson, birth-and-death, etc.) |
| 60G50 | Sums of independent random variables; random walks |
| 60K37 | Processes in random environments |
Keywords:
biased random walk on a Galton-Watson tree; branching random walk; slow movement; random walk in a random environmentReferences:
| [1] | Aidékon, E., Transient random walks in random environment on a Galton-Watson tree, Probab. Theory Relat. Fields, 142, 525-559 (2008) · Zbl 1146.60078 · doi:10.1007/s00440-007-0114-x |
| [2] | Aidékon, E., Large deviations for transient random walks in random environment on a Galton-Watson tree, Ann. Inst. H. Poincaré Probab. Statist., 46, 159-189 (2010) · Zbl 1191.60119 · doi:10.1214/09-AIHP204 |
| [3] | Ben Arous, G., Fribergh, A., Gantert, N., Hammond, A.: Biased random walks on a Galton-Watson tree with leaves (2007). arXiv math.PR/0711.3686 · Zbl 1239.60091 |
| [4] | Ben Arous, G., Hammond, A.: Stable limit laws for randomly biased random walks on trees (2009, in preparation) · Zbl 1254.60094 |
| [5] | Biggins, J. D., The first- and last-birth problems for a multitype age-dependent branching process, Adv. Appl. Probab., 8, 446-459 (1976) · Zbl 0339.60074 · doi:10.2307/1426138 |
| [6] | Biggins, J. D., Chernoff’s theorem in the branching random walk, J. Appl. Probab., 14, 630-636 (1977) · Zbl 0373.60090 · doi:10.2307/3213469 |
| [7] | Biggins, J. D.; Kyprianou, A. E., Seneta-Heyde norming in the branching random walk, Ann. Probab., 25, 337-360 (1997) · Zbl 0873.60062 · doi:10.1214/aop/1024404291 |
| [8] | Billingsley, P., Convergence of Probability Measures (1968), New York: Wiley, New York · Zbl 0172.21201 |
| [9] | Borodin, A. N.; Salminen, P., Handbook of Brownian motion—acts and Formulae (2002), Basel: Birkhäuser, Basel · Zbl 1012.60003 · doi:10.1007/978-3-0348-8163-0 |
| [10] | Fang, M.; Zeitouni, O., Consistent minimal displacement of branching random walks, Electron. Commun. Probab., 15, 106-118 (2010) · Zbl 1201.60041 · doi:10.1214/ECP.v15-1533 |
| [11] | Faraud, G., A central limit theorem for random walk in a random environment on marked Galton-Watson trees, Electron. J. Probab., 16, 174-215 (2011) · Zbl 1228.60115 · doi:10.1214/EJP.v16-851 |
| [12] | Feller, W., An Introduction to Probability and its Applications, 2 edn., vol. II (1971), New York: Wiley, New York · Zbl 0219.60003 |
| [13] | Gantert, N., Hu, Y., Shi, Z.: Asymptotics for the survival probability in a killed branching random walk. ArXiv math.PR/0811.0262 (2008) · Zbl 1210.60093 |
| [14] | Golosov, A. O., Localization of random walks in one-dimensional random environments, Commun. Math. Phys., 92, 491-506 (1984) · Zbl 0534.60065 · doi:10.1007/BF01215280 |
| [15] | Harris, T. E., The Theory of Branching Processes (1963), Berlin: Springer, Berlin · Zbl 0117.13002 · doi:10.1007/978-3-642-51866-9 |
| [16] | Hu, Y.; Shi, Z., Extreme lengths in Brownian and Bessel excursions, Bernoulli, 3, 387-402 (1997) · Zbl 0907.60036 · doi:10.2307/3318455 |
| [17] | Hu, Y.; Shi, Z., A subdiffusive behaviour of recurrent random walk in random environment on a regular tree, Probab. Theory Relat. Fields, 138, 521-549 (2007) · Zbl 1113.60096 · doi:10.1007/s00440-006-0036-z |
| [18] | Hu, Y.; Shi, Z., Slow movement of recurrent random walk in random environment on a regular tree, Ann. Probab., 35, 1978-1997 (2007) · Zbl 1124.60083 · doi:10.1214/009117906000001150 |
| [19] | Hu, Y.; Shi, Z., Minimal position and critical martingale convergence in branching random walks, and directed polymers on disordered trees, Ann. Probab., 37, 742-789 (2009) · Zbl 1169.60021 · doi:10.1214/08-AOP419 |
| [20] | Jaffuel, B.: The critical barrier for the survival of the branching random walk with absorption (2009). arXiv math.PR/0911.2227 · Zbl 1263.60076 |
| [21] | Kahane, J.-P.; Peyrière, J., Sur certaines martingales de Mandelbrot, Adv. Math., 22, 131-145 (1976) · Zbl 0349.60051 · doi:10.1016/0001-8708(76)90151-1 |
| [22] | Lyons, R., Random walks and percolation on trees, Ann. Probab., 18, 931-958 (1990) · Zbl 0714.60089 · doi:10.1214/aop/1176990730 |
| [23] | Lyons, R., Random walks, capacity and percolation on trees, Ann. Probab., 20, 2043-2088 (1992) · Zbl 0766.60091 · doi:10.1214/aop/1176989540 |
| [24] | Lyons, R.; Athreya, K. B.; Jagers, P., A simple path to Biggins’ martingale convergence for branching random walk, Classical and Modern Branching Processes IMA Volumes in Mathematics and its Applications, vol 84, 217-221 (1997), New York: Springer, New York · Zbl 0897.60086 |
| [25] | Lyons, R.; Pemantle, R., Random walk in a random environment and first-passage percolation on trees, Ann. Probab., 20, 125-136 (1992) · Zbl 0751.60066 · doi:10.1214/aop/1176989920 |
| [26] | Lyons, R.; Pemantle, R.; Peres, Y., Conceptual proofs of Llog L criteria for mean behavior of branching processes, Ann. Probab., 23, 1125-1138 (1995) · Zbl 0840.60077 · doi:10.1214/aop/1176988176 |
| [27] | Lyons, R.; Pemantle, R.; Peres, Y., Ergodic theory on Galton-Watson trees: speed of random walk and dimension of harmonic measure, Ergod. Theory Dyn. Syst., 15, 593-619 (1995) · Zbl 0819.60077 · doi:10.1017/S0143385700008543 |
| [28] | Lyons, R.; Pemantle, R.; Peres, Y., Biased random walks on Galton-Watson trees, Probab. Theory Relat. Fields, 106, 249-264 (1996) · Zbl 0859.60076 · doi:10.1007/s004400050064 |
| [29] | McDiarmid, C., Minimal positions in a branching random walk, Ann. Appl. Probab., 5, 128-139 (1995) · Zbl 0836.60089 · doi:10.1214/aoap/1177004832 |
| [30] | Menshikov, M.V., Petritis, D.: On random walks in random environment on trees and their relationship with multiplicative chaos. In: Mathematics and Computer Science II (Versailles, 2002), pp. 415-422. Birkhäuser, Basel (2002) · Zbl 1027.60101 |
| [31] | Mogulskii, A. A., Small deviations in the space of trajectories, Theory Probab. Appl., 19, 726-736 (1974) · Zbl 0326.60061 · doi:10.1137/1119081 |
| [32] | Peres, Y.; Zeitouni, O., A central limit theorem for biased random walks on Galton-Watson trees, Probab. Theory Relat. Fields, 140, 595-629 (2008) · Zbl 1141.60073 · doi:10.1007/s00440-007-0077-y |
| [33] | Sinai, Ya. G., The limiting behavior of a one-dimensional random walk in a random medium, Th. Probab. Appl., 27, 256-268 (1982) · Zbl 0505.60086 · doi:10.1137/1127028 |
| [34] | Zeitouni, O.: Random Walks in Random Environment. In: XXXI Summer School in Probability, St Flour (2001). Lecture Notes in Math., vol. 1837, pp. 193-312. Springer, Berlin (2004) · Zbl 1060.60103 |
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.
