m
• D

F Nous contacter

0

Post-edited

H 2 Sampling algorithms and phase transitions

Auteurs : Randall, Dana
CIRM (Editeur )

 Loading the player... monotonic surfaces Markov chains integer partitions Boltzmann sampling the 6-vertex model slow mixing

Résumé : Markov chain Monte Carlo methods have become ubiquitous across science and engineering to model dynamics and explore large combinatorial sets. Over the last 20 years there have been tremendous advances in the design and analysis of efficient sampling algorithms for this purpose. One of the striking discoveries has been the realization that many natural Markov chains undergo phase transitions, whereby they abruptly change from being efficient to inefficient as some parameter of the system is modified. Generating functions can offer an alternative approach to sampling and they play a role in showing when certain Markov chains are efficient or not. We will explore the interplay between Markov chains, generating functions, and phase transitions for a variety of combinatorial problems, including graded posets, Boltzmann sampling, and 3-colorings on $Z^{2}$.

Keywords : Markov chain # phase transition # integer partitions # 3-colorings

Codes MSC :
60C05 - Combinatorial probability
60J20 - Applications of Markov chains and discrete-time Markov processes on general state spaces
68R05 - Combinatorics in connection with computer science

Ressources complémentaires :
https://www.cirm-math.fr/RepOrga/1940/Slides/Randall-slides.pdf

 Informations sur la Vidéo Réalisateur : Hennenfent, Guillaume Langue : Anglais Date de publication : 26/07/2019 Date de captation : 24/06/2019 Collection : Research talks Format : MP4 (.mp4) - HD Durée : 01:10:29 Domaine : Computer Science ; Combinatorics ; Probability & Statistics Audience : Chercheurs ; Doctorants , Post - Doctorants Download : https://videos.cirm-math.fr/2019-06-24_Randall.mp4 Informations sur la rencontre Nom de la rencontre : AofA: Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms / AofA: méthodes probabilistes, combinatoires et asymptotiques pour l analyse d algorithmesOrganisateurs de la rencontre : Bassino, Frédérique ; Martínez, Conrado ; Salvy, BrunoDates : 24/06/2019 - 28/06/2019 Année de la rencontre : 2019 URL Congrès : https://conferences.cirm-math.fr/1940.html Citation Data DOI : 10.24350/CIRM.V.19540103 Cite this video as: Randall, Dana (2019). Sampling algorithms and phase transitions. CIRM. Audiovisual resource. doi:10.24350/CIRM.V.19540103 URI : http://dx.doi.org/10.24350/CIRM.V.19540103

### Voir aussi

Bibliographie

• LUBY, Michael, RANDALL, Dana, et SINCLAIR, Alistair. Markov chain algorithms for planar lattice structures. SIAM journal on Computing, 2001, vol. 31, no 1, p. 167-192. - https://doi.org/10.1137/S0097539799360355

• BHAKTA, Prateek, COUSINS, Ben, FAHRBACH, Matthew, et al. Approximately sampling elements with fixed rank in graded posets. In : Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, 2017. p. 1828-1838. - https://doi.org/10.1137/1.9781611974782.119

• FAHRBACH, Matthew et RANDALL, Dana. Slow Mixing of Glauber Dynamics for the Six-Vertex Model in the Ferroelectric and Antiferroelectric Phases. arXiv preprint arXiv:1904.01495, 2019. - https://arxiv.org/abs/1904.01495

Z