Characterizing limits and opportunities in speeding up Markov chain mixing

STOCHASTIC PROCESSES AND THEIR APPLICATIONS

卷:136

Article

Apers, Simon^1,2,7  Sarlette, Alain^3,4  Ticozzi, Francesco^5,6 

[1] CWI, Amsterdam, Netherlands

[2] Univ Libre Bruxelles, QuIC, Brussels, Belgium

[3] Inria Paris, Paris, France

[4] Univ Ghent, Dept Elect & Informat Syst, Ghent, Belgium

[5] Univ Padua, Dipartimento Ingn Informaz, Padua, Italy

[6] Dartmouth Coll, Dept Phys & Astron, Hanover, NH 03755 USA

[7] Univ Ghent, Ghent, Belgium

关键词: Markov chains;    Mixing time;    Algorithm design and analysis;    Network theory (graphs);   

DOI  :  10.1016/j.spa.2021.03.006

来源: Elsevier

【 摘 要 】

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.

【 授权许可】

Free