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.
Type de document :
Communication dans un congrès
IEEE Conference on Decision and Control, Dec 2017, Melbourne, Australia
Liste complète des métadonnées

Littérature citée [22 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01634630
Contributeur : Alain Sarlette <>
Soumis le : mardi 14 novembre 2017 - 12:38:17
Dernière modification le : jeudi 23 novembre 2017 - 15:34:02

Fichier

Mixing-CDC-Final.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01634630, version 1

Collections

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〉

Partager

Métriques

Consultations de la notice

160

Téléchargements de fichiers

37