A Technique for Lower Bounding the Cover Time
- 1 February 1992
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Discrete Mathematics
- Vol. 5 (1) , 81-87
- https://doi.org/10.1137/0405007
Abstract
We give a general technique for proving lower bounds on expected covering times of random walks on graphs in terms of expected hitting times between vertices. We use this teclmique to prove:Keywords
This publication has 12 references indexed in Scilit:
- Random walk covering of some special treesJournal of Mathematical Analysis and Applications, 1991
- Coalescing Random Walks and Voter Model Consensus Times on the Torus in $\mathbb{Z}^d$The Annals of Probability, 1989
- Hitting times for random walks on vertex-transitive graphsMathematical Proceedings of the Cambridge Philosophical Society, 1989
- On the cover time of random walks on graphsJournal of Theoretical Probability, 1989
- Bounds on the cover timeJournal of Theoretical Probability, 1989
- Lower bounds for covering times for reversible Markov chains and random walks on graphsJournal of Theoretical Probability, 1989
- Covering Problems for Brownian Motion on SpheresThe Annals of Probability, 1988
- On the time taken by random walks on finite groups to visit every stateProbability Theory and Related Fields, 1983
- Random walks, universal traversal sequences, and the complexity of maze problemsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1979
- Markov Chain Models — Rarity and ExponentialityPublished by Springer Nature ,1979