New bounds for edge-cover by random walk

DOI10.1017/S096354831400008XMaRDI QIDQ5495676zbMATH OpenOpenAlexFDO

Authors Peter Winkler, Agelos Georgakopoulos

Publication date 6 August 2014

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1109.6619

zbMATH Keywords

edge-cover time

Mathematics Subject Classification ID

Random walks on graphs (05C81) Brownian motion (60J65)

Abstract: We show that the expected time for a random walk on a (multi-)graph $G$ to traverse all $m$ edges of $G$, and return to its starting point, is at most $2m^2$; if each edge must be traversed in both directions, the bound is $3m^2$. Both bounds are tight and may be applied to graphs with arbitrary edge lengths, with implications for Brownian motion on a finite or infinite network of total edge-length $m$.

Recommendations

• On the time to traverse all edges of a graph
• Random Walks on Regular and Irregular Graphs
• A bound for the covering time of random walks on graphs
• On the cover time of random walks on graphs
• Short Random Walks on Graphs

Cites work

• A tight upper bound on the cover time for random walks on graphs
• Cover times for Brownian motion and random walks in two dimensions
• Cover times, blanket times, and majorizing measures
• Covering times of random walks on bounded degree trees and other graphs
• Extremal cover times for random walks on trees
• Graph-like continua, augmenting arcs, and Menger's theorem
• scientific article; zbMATH DE number 5321044 (Why is no real title available?)
• Maximum hitting time for random walks on graphs
• Multiple cover time
• On Cumulative Sums of Random Variables
• On the cover time of random walks on graphs
• On the time to traverse all edges of a graph
• Probability on trees and networks
• Random motion on binary trees
• Random walks and the effective resistance of networks
• The equivalence of diffusions on networks to Brownian motion
• Uniqueness of electrical currents in a network of finite total resistance

Cited in

(4)

• On the time to traverse all edges of a graph
• Short Random Walks on Graphs
• Brownian motion on graph-like spaces
• Improved upper bounds for Random-Edge and Random-Jump on abstract cubes

This page was built for publication: New bounds for edge-cover by random walk

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5495676)