When Does Memory Speed-up Mixing?

Simon Apers 1 Alain Sarlette 2 Francesco Ticozzi 3
2 QUANTIC - QUANTum Information Circuits
ENS Paris - École normale supérieure - Paris, UPMC - Université Pierre et Marie Curie - Paris 6, MINES ParisTech - É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 metadatas

Cited literature [22 references]  Display  Hide  Download

https://hal.inria.fr/hal-01634630
Contributor : Alain Sarlette <>
Submitted on : Tuesday, November 14, 2017 - 12:38:17 PM
Last modification on : Wednesday, May 15, 2019 - 3:36:17 AM
Long-term archiving on : Thursday, February 15, 2018 - 3:57:16 PM

File

Mixing-CDC-Final.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01634630, version 1

Citation

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

Share

Metrics

Record views

574

Files downloads

242