Lower bounds for covering times for reversible Markov chains and random walks on graphs
From MaRDI portal
Publication:1825525
DOI10.1007/BF01048272zbMath0684.60055MaRDI QIDQ1825525
Publication date: 1989
Published in: Journal of Theoretical Probability (Search for Journal in Brave)
Related Items (34)
Cutoffs for product chains ⋮ Random walks on graphs with interval weights and precise marginals ⋮ Analytical results for the distribution of cover times of random walks on random regular graphs ⋮ On the cover time and mixing time of random geometric graphs ⋮ Covering with blocks in the non-symmetric case ⋮ On the mean and variance of cover times for random walks on graphs ⋮ Stochastic forms of non-negative matrices and Perron-regularity ⋮ Poisson approximation for non-backtracking random walks ⋮ Sandwich theorem of cover times ⋮ A tight lower bound on the cover time for random walks on graphs ⋮ Multiple random walks on graphs: mixing few to cover many ⋮ Markov chains on hypercubes: Spectral representations and several majorization relations ⋮ A lecture on the averaging process ⋮ Cover times, blanket times, and majorizing measures ⋮ Random walks on highly symmetric graphs ⋮ On the time to traverse all edges of a graph ⋮ Waiting for regulatory sequences to appear ⋮ How universal are asymptotics of disconnection times in discrete cylinders? ⋮ A semidefinite bound for mixing rates of Markov chains ⋮ A model of self‐avoiding random walks for searching complex networks ⋮ Greedy Random Walk ⋮ Laplace eigenvalues of graphs---a survey ⋮ One-dimensional stepping stone models, sardine genetics and Brownian local time ⋮ Random walks which prefer unvisited edges: Exploring high girth even degree expanders in linear time ⋮ Effective graph resistance ⋮ New bounds for randomized busing ⋮ Many Random Walks Are Faster Than One ⋮ Reversibility of the non-backtracking random walk ⋮ Coupling and mixing times in a Markov chain ⋮ Probabilistic embedding of discrete sets as continuous metric spaces ⋮ Bounds on the cover time ⋮ On the fastest finite Markov processes ⋮ Simple permutations mix well ⋮ Random walk covering of some special trees
Cites Work
This page was built for publication: Lower bounds for covering times for reversible Markov chains and random walks on graphs
