Large deviations for random walks on Galton-Watson trees: averaging and uncertainty

• 成果类型: Article
• 署名作者: Dembo, A; Gantert, N; Peres, Y; Zeitouni, O
• 署名单位: Stanford University; Stanford University; Helmholtz Association; Karlsruhe Institute of Technology; Hebrew University of Jerusalem; University of California System; University of California Berkeley; Technion Israel Institute of Technology
• 刊物名称: PROBABILITY THEORY AND RELATED FIELDS
• ISSN/ISSBN: 0178-8051
• DOI: 10.1007/s004400100162
• 发表日期: 2002
• 页码: 241-288
• 关键词: dimensional random-walk; random environment; speed

摘要

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 lambda-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).