| We study the relationship between random walk and geometry on graphs of exponential growth. In the first chapter we introduce a tool that might be useful in other settings: a new lower bound for the hitting time of a set for a random walk on a graph in terms of distance, volume and electric resistance.;The second chapter uses this result to give upper bounds for the linear rate of escape of the random walk in terms of the geometry of the graph, answering questions posed by Lyons, Pemantle and Peres (1997). 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.;The third chapter studies anchored expansion, a non-uniform version of the strong isoperimetric inequality. We show that every graph with i-anchored expansion contains a subgraph with isoperimetric (Cheeger) constant of at least i. We prove a conjecture by Benjamini, Lyons and Schramm (1999) that in such graphs the random walk escapes with a positive lim inf speed. We also show that anchored expansion implies that the heat-kernel decays at a sub-exponential rate of at least exp(-- cn1/3). |
