Skip to Main content Skip to Navigation
New interface
Conference papers

When Does Memory Speed-up Mixing?

Simon Apers 1 Alain Sarlette 2 Francesco Ticozzi 3 
2 QUANTIC - QUANTum Information Circuits
ENS-PSL - École normale supérieure - Paris, UPMC - Université Pierre et Marie Curie - Paris 6, Mines Paris - PSL (École nationale supérieure des mines de Paris), Inria de Paris
Abstract : We investigate under which conditions a higher-order Markov chain, or more generally a Markov chain on an extended state space, can mix faster than a standard Markov chain on a graph of interest. We find that, depending on the constraints on the dynamics, two very different scenarios can emerge: under strict invariance of the target marginal and for general initialization of the lifted chain no speedup is possible; on the other hand, if these requirements are both relaxed, the lifted dynamics can achieve mixing in a time that corresponds to the diameter of the graph, which is optimal.
Complete list of metadata

Cited literature [22 references]  Display  Hide  Download
Contributor : Alain Sarlette Connect in order to contact the contributor
Submitted on : Tuesday, November 14, 2017 - 12:38:17 PM
Last modification on : Friday, November 18, 2022 - 9:24:55 AM
Long-term archiving on: : Thursday, February 15, 2018 - 3:57:16 PM


Files produced by the author(s)


  • HAL Id : hal-01634630, version 1


Simon Apers, Alain Sarlette, Francesco Ticozzi. When Does Memory Speed-up Mixing?. IEEE Conference on Decision and Control, Dec 2017, Melbourne, Australia. ⟨hal-01634630⟩



Record views


Files downloads