On the speed of random walks on graphs

• 成果类型: Article
• 署名作者: Virág, B
• 署名单位: University of California System; University of California Berkeley
• 刊物名称: ANNALS OF PROBABILITY
• ISSN/ISSBN: 0091-1798
• 发表日期: 2000
• 页码: 379-394
• 关键词: galton-watson trees; biased random-walks; percolation

摘要

Lyons, Pemantle and Peres asked whether the asymptotic lower speed in an infinite tree is bounded by the asymptotic speed in the regular tree with the same average number of branches. In the more general setting of random walks on graphs, we establish a bound on the expected value of the exit time from a vertex set in terms of the size and distance from the origin of its boundary, and prove this conjecture. We give sharp bounds for limiting speed (or, when applicable, sublinear rate of escape) in terms of growth propel ties of the graph. For trees, we get a bound for the speed in terms of the Hausdorff dimension of the harmonic measure on the boundary. As a consequence, two conjectures of Lyons, Pemantle and Peres are resolved, and a new bound is given for the dimension of the harmonic measure defined by the biased random walk on a Galton-Watson tree.