Expected hitting time estimates on finite graphs

Vienna Probability Seminar

The expected hitting time from vertex a to vertex b, H(a,b), is the expected value of the time it takes a random walk starting at a to reach b. In this talk, we shall discuss estimates for H(a,b) when the distance between a and b is comparable to the diameter of the graph, and the graph satisfies a Harnack condition. We show that, in such cases, H(a,b) can be estimated using a formula in terms of the volumes of balls around b. We give an outline of the proof using Green functions and heat kernel estimates. Using this result, we can then estimate H(a,b) on various graphs, such as rectangular tori, some convex traces on the integer lattice, and fractal graphs.

Joint work with Laurent Saloff-Coste.