Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

Lifting Markov Chains To Mix Faster: Limits and Opportunities

Simon Apers 1 Francesco Ticozzi 2 Alain Sarlette 3
3 QUANTIC - QUANTum Information Circuits
ENS Paris - École normale supérieure - Paris, MINES ParisTech - École nationale supérieure des mines de Paris, SU - Sorbonne Université, Inria de Paris
Abstract : Lifted Markov chains are Markov chains on graphs with added local "memory" and can be used to mix towards a target distribution faster than their memoryless counterparts. Upper and lower bounds on the achievable performance have been provided under specific assumptions. In this paper, we analyze which assumptions and constraints are relevant for mixing, and how changing these assumptions affects those bounds. Explicitly, we find that requesting mixing on either the original or the full lifted graph, and allowing for reducible lifted chains or not, have no essential influence on mixing time bounds. On the other hand, allowing for suitable initialization of the lifted dynamics and/or imposing invariance of the target distribution for any initialization do significantly affect the convergence performance. The achievable convergence speed for a lifted chain goes from diameter-time to no acceleration over a standard Markov chain, with conductance bounds limiting the effectiveness of the intermediate cases. In addition, we show that the relevance of imposing ergodic flows depends on the other criteria. The presented analysis allows us to clarify in which scenarios designing lifted dynamics can lead to better mixing, and provide a flexible framework to compare lifted walks with other acceleration methods.
Document type :
Preprints, Working Papers, ...
Complete list of metadata
Contributor : Alain Sarlette Connect in order to contact the contributor
Submitted on : Tuesday, January 5, 2021 - 2:12:23 PM
Last modification on : Friday, December 3, 2021 - 11:43:31 AM

Links full text


  • HAL Id : hal-03097637, version 1
  • ARXIV : 1705.08253


Simon Apers, Francesco Ticozzi, Alain Sarlette. Lifting Markov Chains To Mix Faster: Limits and Opportunities. 2021. ⟨hal-03097637⟩



Record views