Many Random Walks Are Faster Than One

Details Many Random Walks Are Faster Than One Many Random Walks Are Faster Than One

2007-05-03

arxiv.org/abs/0705.0467v2

Mathematics

Probability

15 pages

Scientific paper

We pose a new and intriguing question motivated by distributed computing regarding random walks on graphs: How long does it take for several independent random walks, starting from the same vertex, to cover an entire graph? We study the cover time - the expected time required to visit every node in a graph at least once - and we show that for a large collection of interesting graphs, running many random walks in parallel yields a speed-up in the cover time that is linear in the number of parallel walks. We demonstrate that an exponential speed-up is sometimes possible, but that some natural graphs allow only a logarithmic speed-up. A problem related to ours (in which the walks start from some probabilistic distribution on vertices) was previously studied in the context of space efficient algorithms for undirected s-t connectivity and our results yield, in certain cases, an improvement upon some of the earlier bounds.

Affiliated with

Also associated with

No associations

Rating

Many Random Walks Are Faster Than One does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Many Random Walks Are Faster Than One, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Many Random Walks Are Faster Than One will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-497179