How Slow, or Fast, Are Standard Random Walks? – Analyses of Hitting and Cover Times on Tree

Nonaka, Y., Ono, H., Kijima, S. and Yamashita, M.

Random walk is a powerful tool, not only for modeling, but also for practical use such as the Internet crawlers. Standard random walks on graphs have been well studied; It is well-known that both hitting time and cover time of a standard random walk are bounded by O(n3) for any graph with n vertices, besides the bound is tight for some graphs. Ikeda et al. (2003) provided “β-random walk,” which real- izes O(n2) hitting time and O(n2 log n) cover times for any graph, thus it archives, in a sense, “n-times improvement” compared to the standard random walk. This paper is concerned with optimizations of hitting and cover times, by drawing a comparison between the standard random walk and the fastest random walk. We show for any tree that the hitting time of the standard random walk is at most O(√n)-times longer than one of the fastest random walk. Similarly, the cover time of the standard random walk is at most O( √ n log n)-times longer than the fastest one, for any tree. We also show that our bound for the hitting time is tight by giving examples, while we only give a lower bound Ω( n/logn) for the cover time.

Cite as: Nonaka, Y., Ono, H., Kijima, S. and Yamashita, M. (2011). How Slow, or Fast, Are Standard Random Walks? – Analyses of Hitting and Cover Times on Tree. In Proc. Computing: The Australasian Theory Symposium (CATS 2011) Perth, Australia. CRPIT, 119. Alex Potanin and Taso Viglas Eds., ACS. 63-68

(from crpit.com) (local if available)