2011/09/29 by Agelos Georgakopoulos, AGELOS GEORGAKOPOULOS, Peter Winkler +1
Biochemistry, Genetics and Molecular Biology · Computer Science · Mathematics · #Brownian motion #Diffusion and Search Dynamics #Enhanced Data Rates for GSM Evolution #Heterogeneous random walk in one dimension #Markov Chains and Monte Carlo Methods #Metric (unit) #Random walk #Stochastic processes and statistical mechanics #Traverse #Upper and lower bounds #cs.DM #math.CO #msc:05C81
paper · pdf · doi:10.1017/s096354831400008x
published as Combinator. Probab. Comp. 23 (2014) 571-584
arxiv created 2011/09/29 · openalex publication_date 2014/03/11 · openalex created_date 2016/06/24 · arxiv updated 2019/02/20 · openalex updated_date 2026/08/05
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 2 m 2 ; if each edge must be traversed in both directions, the bound is 3 m 2 . Both bounds are tight and may be applied to graphs with arbitrary edge lengths. This has interesting implications for Brownian motion on certain metric spaces, including some fractals.