Fast graphs for the random walker

 Consider the time T _oz when the random walk on a weighted graph started at the vertex o first hits the vertex set z. We present lower bounds for T _oz in terms of the volume of z and the graph distance between o and z. The bounds are for expected value and large deviations, and are asymptotically sharp. We deduce rate of escape results for random walks on infinite graphs of exponential or polynomial growth, and resolve a conjecture of Benjamini and Peres. Received: 31 October 2000 / Revised version: 5 January 2002 / Published online: 22 August 2002