Journal
STOCHASTIC PROCESSES AND THEIR APPLICATIONS
Volume 136, Issue -, Pages 145-191Publisher
ELSEVIER
DOI: 10.1016/j.spa.2021.03.006
Keywords
Markov chains; Mixing time; Algorithm design and analysis; Network theory (graphs)
Categories
Ask authors/readers for more resources
This paper explores various methods to accelerate Markov chain mixing, finding that some approaches can speed up mixing time while others do not allow for any speedup.
A variety of paradigms have been proposed to speed up Markov chain mixing, ranging from non-backtracking random walks to simulated annealing and lifted Metropolis-Hastings. We provide a general characterization of the limits and opportunities of different approaches for designing fast mixing dynamics on graphs using the framework of lifted Markov chains. This common framework allows to prove lower and upper bounds on the mixing behavior of these approaches, depending on a limited set of assumptions on the dynamics. We find that some approaches can speed up the mixing time to diameter time, or a time inversely proportional to the graph conductance, while others allow for no speedup at all. (C) 2021 Elsevier B.V. All rights reserved.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available