Abstract.
In the study of large deviations for random walks in random environment, a key distinction has emerged between quenched asymptotics, conditional on the environment, and annealed asymptotics, obtained from averaging over environments. In this paper we consider a simple random walk {X n } on a Galton–Watson tree T, i.e., on the family tree arising from a supercritical branching process. Denote by |X n | the distance between the node X n and the root of T. Our main result is the almost sure equality of the large deviation rate function for |X n |/n under the “quenched measure” (conditional upon T), and the rate function for the same ratio under the “annealed measure” (averaging on T according to the Galton–Watson distribution). This equality hinges on a concentration of measure phenomenon for the momentum of the walk. (The momentum at level n, for a specific tree T, is the average, over random walk paths, of the forward drift at the hitting point of that level). This concentration, or certainty, is a consequence of the uncertainty in the location of the hitting point. We also obtain similar results when {X n } is a λ-biased walk on a Galton–Watson tree, even though in that case there is no known formula for the asymptotic speed. Our arguments rely at several points on a “ubiquity” lemma for Galton–Watson trees, due to Grimmett and Kesten (1984).
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
Author information
Authors and Affiliations
Additional information
Received: 15 November 2000 / Revised version: 27 February 2001 / Published online: 19 December 2001
Rights and permissions
About this article
Cite this article
Dembo, A., Gantert, N., Peres, Y. et al. Large deviations for random walks on Galton–Watson trees: averaging and uncertainty. Probab Theory Relat Fields 122, 241–288 (2002). https://doi.org/10.1007/s004400100162
Issue Date:
DOI: https://doi.org/10.1007/s004400100162