期刊
STOCHASTIC PROCESSES AND THEIR APPLICATIONS
卷 136, 期 -, 页码 145-191出版社
ELSEVIER
DOI: 10.1016/j.spa.2021.03.006
关键词
Markov chains; Mixing time; Algorithm design and analysis; Network theory (graphs)
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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据