Many Random Walks Are Faster Than One
From MaRDI portal
Publication:5199503
DOI10.1017/S0963548311000125zbMATH Open1223.05284arXiv0705.0467MaRDI QIDQ5199503FDOQ5199503
Authors: Noga Alon, Chen Avin, Michal Koucký, Gady Kozma, Zvi Lotker, Mark Tuttle 
Publication date: 16 August 2011
Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)
Abstract: 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.
Full work available at URL: https://arxiv.org/abs/0705.0467
Recommendations
- A permuted random walk exits faster
- More randomness of environment does not always slow down a random walk
- Fastest random walk on a path
- scientific article; zbMATH DE number 1827973
- Fast distributed random walks
- NON-BACKTRACKING RANDOM WALKS MIX FASTER
- Random walks with multiple step lengths
- On the speed of a cookie random walk
Cites Work
- Eigenvalues and expanders
- A spectrum of time-space trade-offs for undirected \(s-t\) connectivity
- Lower bounds for covering times for reversible Markov chains and random walks on graphs
- A tight upper bound on the cover time for random walks on graphs
- A tight lower bound on the cover time for random walks on graphs
- Threshold limits for cover times
- On the time taken by random walks on finite groups to visit every state
- Covering problems for Brownian motion on spheres
- An O (log( n ) 4/3 ) space algorithm for ( s, t ) connectivity in undirected graphs
- On the cover time of planar graphs
- Bounds on the cover time
- On the Cover Time for Random Walks on Random Graphs
- Covering times of random walks on bounded degree trees and other graphs
- An optimal randomised logarithmic time connectivity algorithm for the EREW PRAM
- Fast Connected Components Algorithms for the EREW PRAM
Cited In (32)
- Speeding up random walks with neighborhood exploration
- The multi-agent rotor-router on the ring: a deterministic alternative to parallel random walks
- Spanders: distributed spanning expanders
- Self-Stabilizing and Self-Organizing Virtual Infrastructures for Mobile Networks
- A general lower bound for collaborative tree exploration
- Expansion and the cover time of parallel random walks
- Bounds on the cover time of parallel rotor walks
- Spread of information and diseases via random walks in sparse graphs
- Active exploration for large graphs
- On an epidemic model on finite graphs
- Does adding more agents make a difference? A case study of cover time for the rotor-router
- Tight bounds for the cover time of multiple random walks
- The hitting time of multiple random walks
- Memory Efficient Anonymous Graph Exploration
- Broadcasting on paths and cycles
- Multiple Random Walks and Interacting Particle Systems
- On Coalescence Time in Graphs: When Is Coalescing as Fast as Meeting?
- The cover time of a (multiple) Markov chain with rational transition probabilities is rational
- Multiple random walks on graphs: mixing few to cover many
- Multiple random walks in random regular graphs
- Random walks, bisections and gossiping in circulant graphs
- Collective search and decision-making for target localization
- Analytical results for the distribution of cover times of random walks on random regular graphs
- Searching without communicating: tradeoffs between performance and selection complexity
- Coalescing walks on rotor-router systems
- Tight Bounds for the Cover Time of Multiple Random Walks
- The ANTS problem
- Multiple random walks on paths and grids
- The power of two choices for random walks
- Distributed computation in dynamic networks via random walks
- Lower bounds for searching robots, some faulty
- Motifs for processes on networks
This page was built for publication: Many Random Walks Are Faster Than One
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5199503)
