F Nous contacter


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 :

    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 ; Combinatorics ; Computer Science ; Probability and Statistics
    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 algorithmes
Organisateurs de la rencontre : Bassino, Frédérique ; Martínez, Conrado ; Salvy, Bruno
Dates : 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


  • 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