Expected hitting time estimates on finite graphs
Preprint
Abstract
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 paper, we give 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 in terms of the volumes of balls around $b$. Using our results, we estimate $H(a,b)$ on various graphs, such as rectangular tori, some convex traces in $\mathbb{Z}^d$, and fractal graphs. Our proofs use heat kernel estimates.
Keywords
All Related Versions
This publication has 7 references indexed in Scilit:
- Analytic-geometric methods for finite Markov chains with applications to quasi-stationarityLatin American Journal of Probability and Mathematical Statistics, 2020
- Random Walks and Heat Kernels on Graphs2017
- Characterization of sub‐Gaussian heat kernel estimates on strongly recurrent graphsCommunications on Pure and Applied Mathematics, 2005
- Mixing Times for Random Walks on Finite Lamplighter GroupsElectronic Journal of Probability, 2004
- Stability of parabolic Harnack inequalitiesTransactions of the American Mathematical Society, 2003
- Nash inequalities for finite Markov chainsJournal of Theoretical Probability, 1996
- Coalescing Random Walks and Voter Model Consensus Times on the Torus in $\mathbb{Z}^d$The Annals of Probability, 1989