Probabilistic techniques for analyzing sampling algorithms and the dynamics of lattice models

Lattice models;Markov chain Monte Carlo;Sampling algorithms;Statistical physics

Fahrbach, Matthew ; Randall, Dana Computer Science Peng, Richard Singh, Mohit Tetali, Prasad Vigoda, Eric ; Randall, Dana

University:Georgia Institute of Technology

Department:Computer Science

关键词: Lattice models;    Markov chain Monte Carlo;    Sampling algorithms;    Statistical physics;   

Others  :  https://smartech.gatech.edu/bitstream/1853/62274/1/FAHRBACH-DISSERTATION-2019.pdf

美国|英语

来源: SMARTech Repository

【 摘 要 】

Statistical mechanics bridges the fields of physics and probability theory, providing critical insights into both disciplines. Statistical physics models capture key features of macroscopic phenomena and consist of a set of configurations satisfying various constraints. Markov chain Monte Carlo algorithms are often used to sample from distributions over the exponentially large state space of these models to gain insight about the system and estimate its thermodynamic properties. Similar problems arise throughout machine learning, optimization, and counting complexity. In this dissertation, we present several new techniques based on random walks for analyzing sampling algorithms and the dynamics of various lattice models from statistical physics. We start by investigating the mixing time of Glauber dynamics for the six-vertex model in its ordered phases. We show that for every Boltzmann weight in the ferroelectric phase, there exist boundary conditions such that local Markov chains require exponential time to converge to equilibrium. This is the first rigorous result about the mixing time of Glauber dynamics for the six-vertex model in the ferroelectric phase. We also analyze the Glauber dynamics with free boundary conditions in the antiferroelectric phase and significantly extend the region for which local Markov chains are known to be slow mixing. In separate lines of work, we use techniques from the theory of random walks and electrical networks to give nearly tight bounds for the transience class of the Abelian sandpile model, closing an open problem of Babai and Gorodezky. The Abelian sandpile model is the canonical dynamical system used to study the phenomenon of self-organized criticality, and the transience class measures the time needed for the process to reach steady-state behavior. We also explore a new approach for approximately sampling elements with fixed rank from graded posets that relies solely on the mixing time of biased Markov chains. This allows us to bypass the usual obstacle of log-concavity. Last, we take a foray into analytic combinatorics and use the singularity analysis of Dirichlet generating functions to design sampling algorithms for Bose–Einstein condensates.