Characterizing limits and opportunities in speeding up Markov chain mixing

Simon Apers, Alain Sarlette and Francesco Ticozzi

Stochastic Processes and their Applications, 2021, vol. 136, issue C, 145-191

Abstract: 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.

Keywords: Markov chains; Mixing time; Algorithm design and analysis; Network theory (graphs) (search for similar items in EconPapers)
Date: 2021
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S030441492100034X
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:spapps:v:136:y:2021:i:c:p:145-191

Ordering information: This journal article can be ordered from
http://http://www.elsevier.com/wps/find/supportfaq.cws_home/regional
https://shop.elsevie ... _01_ooc_1&version=01

DOI: 10.1016/j.spa.2021.03.006

Access Statistics for this article

Stochastic Processes and their Applications is currently edited by T. Mikosch

More articles in Stochastic Processes and their Applications from Elsevier
Bibliographic data for series maintained by Catherine Liu ().