2018/07/18 by Roberto I. Oliveira, Yuval Peres, Oliveira, Roberto I. +1 · 1 citation
Computer Science · Mathematics · #05C81 #60G50 #60J10 #Complexity and Algorithms in Graphs #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Optimization and Search Problems #Probability (math.PR) #Stochastic processes and statistical mechanics
paper · pdf · doi:10.48550/arxiv.1807.06858
openalex publication_date 2018/07/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We prove new results on lazy random walks on finite graphs. To start, we\nobtain new estimates on return probabilities Pt(x,x) and the maximum\nexpected hitting time t rm hit, both in terms of the relaxation time. We\nalso prove a discrete-time version of the first-named author's ``Meeting time\nlemma"~ that bounds the probability of random walk hitting a deterministic\ntrajectory in terms of hitting times of static vertices. The meeting time\nresult is then used to bound the expected full coalescence time of multiple\nrandom walks over a graph. This last theorem is a discrete-time version of a\nresult by the first-named author, which had been previously conjectured by\nAldous and Fill. Our bounds improve on recent results by Lyons and\nOveis-Gharan; Kanade et al; and (in certain regimes) Cooper et al.\n