Fast graphs for the random walker (Q1849735): Difference between revisions

Let \(T_{oz}\) denote the time when the random walk on a weighted graph started at the vertex \(o\) first hits the vertex set \(z\). The author presents 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 values and large deviations, and are asymptotically sharp. The author also deduces rate of escape results for random walks on infinite graphs of exponential or polynomial growth, and resolves a conjecture of Benjamini and Peres.