Large deviations for transient random walks in random environment on a Galton-Watson tree
Annales de l'I.H.P. Probabilités et statistiques, Volume 46 (2010) no. 1, p. 159-189

Consider a random walk in random environment on a supercritical Galton-Watson tree, and let τn be the hitting time of generation n. The paper presents a large deviation principle for τn/n, both in quenched and annealed cases. Then we investigate the subexponential situation, revealing a polynomial regime similar to the one encountered in one dimension. The paper heavily relies on estimates on the tail distribution of the first regeneration time.

Nous considérons une marche aléatoire en milieu aléatoire sur un arbre de Galton-Watson. Soit τn le temps d'atteinte du niveau n. Le papier présente un principe de grandes déviations pour τn/n, dans les cas quenched et annealed. Nous étudions ensuite le régime sous-exponentiel, qui fait apparaître un régime polynomial rappelant la dimension 1. Le papier repose principalement sur les estimations de la queue de distribution du premier temps de renouvellement.

DOI : https://doi.org/10.1214/09-AIHP204
Classification:  60K37,  60J80,  60F15,  60F10
Keywords: random walk in random environment, law of large numbers, large deviations, Galton-Watson tree
@article{AIHPB_2010__46_1_159_0,
     author = {Aid\'ekon, Elie},
     title = {Large deviations for transient random walks in random environment on a Galton-Watson tree},
     journal = {Annales de l'I.H.P. Probabilit\'es et statistiques},
     publisher = {Gauthier-Villars},
     volume = {46},
     number = {1},
     year = {2010},
     pages = {159-189},
     doi = {10.1214/09-AIHP204},
     zbl = {1191.60119},
     mrnumber = {2641775},
     language = {en},
     url = {http://www.numdam.org/item/AIHPB_2010__46_1_159_0}
}
Aidékon, Elie. Large deviations for transient random walks in random environment on a Galton-Watson tree. Annales de l'I.H.P. Probabilités et statistiques, Volume 46 (2010) no. 1, pp. 159-189. doi : 10.1214/09-AIHP204. http://www.numdam.org/item/AIHPB_2010__46_1_159_0/

[1] E. Aidékon. Transient random walks in random environment on a Galton-Watson tree. Probab. Theory Related Fields 142 (2008) 525-559. | MR 2438700 | Zbl 1146.60078

[2] K. B. Athreya and P. E. Ney. Branching Processes. Springer, New York, 1972. | MR 373040 | Zbl 0259.60002

[3] J. D. Biggins. Martingale convergence in the branching random walk. J. Appl. Probab. 14 (1977) 25-37. | MR 433619 | Zbl 0356.60053

[4] F. Comets and V. Vargas. Majorizing multiplicative cascades for directed polymers in random media. ALEA 2 (2006) 267-277. | MR 2249671 | Zbl 1105.60074

[5] A. Dembo, N. Gantert, Y. Peres and O. Zeitouni. Large deviations for random walks on Galton-Watson trees: Averaging and uncertainty. Probab. Theory Related Fields 122 (2002) 241-288. | MR 1894069 | Zbl 0996.60110

[6] A. Dembo, Y. Peres and O. Zeitouni. Tail estimates for one-dimensional random walk in random environment. Comm. Math. Phys. 181 (1996) 667-683. | MR 1414305 | Zbl 0868.60058

[7] J. Franchi. Chaos multiplicatif: Un traitement simple et complet de la fonction de partition. In Séminaire de Probabilités, XXIX 194-201. Lecture Notes in Math. 1613. Springer, Berlin, 1995. | Numdam | MR 1459460 | Zbl 0834.60101

[8] T. Gross. Marche aléatoire en milieu aléatoire sur un arbre. Ph.D. thesis, 2004.

[9] H. Kesten, M. V. Kozlov and F. Spitzer. A limit law for random walk in a random environment. Compos. Math. 30 (1975) 145-168. | Numdam | MR 380998 | Zbl 0388.60069

[10] Q. Liu. On generalized multiplicative cascades. Stochastic Process. Appl. 86 (2000) 263-286. | MR 1741808 | Zbl 1028.60087

[11] R. Lyons and R. Pemantle. Random walk in a random environment and first-passage percolation on trees. Ann. Probab. 20 (1992) 125-136. | MR 1143414 | Zbl 0751.60066

[12] R. Lyons, R. Pemantle and Y. Peres. Biased random walks on Galton-Watson trees. Probab. Theory Related Fields 106 (1996) 249-264. | MR 1410689 | Zbl 0859.60076

[13] J. Neveu. Arbres et processus de Galton-Watson. Ann. Inst. H. Poincaré Probab. Statist. 22 (1986) 199-207. | Numdam | MR 850756 | Zbl 0601.60082

[14] R. Pemantle and Y. Peres. Critical random walk in random environment on trees. Ann. Probab. 23 (1995) 105-140. | MR 1330763 | Zbl 0837.60066

[15] V. V. Petrov. Sums of Independent Random Variables. Springer, New York, 1975. (Translated from the Russian by A. A. Brown, Ergebnisse der Mathematik und ihrer Grenzgebiete, Band 82.) | MR 388499 | Zbl 0322.60042

[16] D. Piau. Théorème central limite fonctionnel pour une marche au hasard en environment aléatoire. Ann. Probab. 26 (1998) 1016-1040. | MR 1634413 | Zbl 0938.60085

[17] O. Zeitouni. Random walks in random environment. In Lectures on Probability Theory and Statistics 189-312. Lecture Notes in Math. 1837. Springer, Berlin, 2004. | MR 2071631 | Zbl 1060.60103