Lyons, Pemantle and Peres asked whether the asymptoticlower speed in
an infinite tree is bounded by the asymptoticspeed 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 properties of the
graph. For trees, we get a bound for the speed in terms of the Hausdorff
dimension of the harmonicmeasure 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 harmonicmeasure defined by the biased random walk on a
Galton–Watson tree.