Random walks on networks: cumulative distribution of cover time

Abstract

We derive an exact closed-form analytical expression for the distribution of the cover time for a random walk over an arbitrary graph. In special case, we derive simplified exact expressions for the distributions of cover time for a complete graph, a cycle graph, and a path graph. An accurate approximation for the cover time distribution, with computational complexity of O(2n), is also presented. The approximation is numerically tested only for graphs with n<=1000 nodes.

References in corpus (6)

• Search in Power-Law Networks
• Optimal network topologies for local search with congestion
• Optimal search strategies for hidden targets
• First Passage Properties of the Erdos-Renyi Random Graph
• Random walks on complex trees
• Scaling Properties of Random Walks on Small-World Networks

Cited by in corpus (7)

• Networking - A Statistical Physics Perspective
• Manipulation of extreme events on scale-free networks
• Exact distributions of cover times for $N$ independent random walkers in one dimension
• Analytical results for the distribution of cover times of random walks on random regular graphs
• Dynamically accelerated cover times
• Numerical evidence against a conjecture on the cover time of planar graphs
• Records for the number of distinct sites visited by a random walk on the fully-connected lattice