Conferences in Research and Practice in Information Technology
  

Online Version - Last Updated - 20 Jan 2012

 

 
Home
 

 
Procedures and Resources for Authors

 
Information and Resources for Volume Editors
 

 
Orders and Subscriptions
 

 
Published Articles

 
Upcoming Volumes
 

 
Contact Us
 

 
Useful External Links
 

 
CRPIT Site Search
 
    

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
pdf (from crpit.com) pdf (local if available) BibTeX EndNote GS