Back to search

Georgia Institute of Technology

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

Abstract

dc:description.abstract

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.

Degree

thesis:*
Level thesis:degree_level
Doctoral
Department dc:contributor.department
Computer Science
Grantor dc:publisher
Georgia Institute of Technology
Year dc:date.issued
2019

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Fahrbach, Matthew
Advisor dc:contributor.advisor
  • Randall, Dana
Committee members dc:contributor.committeemember
  • Peng, Richard
  • Singh, Mohit
  • Tetali, Prasad
  • Vigoda, Eric

Subjects

dc:subject × 4

Identifiers

dc:identifier.*
Handle dc:identifier.uri
http://hdl.handle.net/1853/62274

Chain of custody

source
Harvested from
Georgia Tech
Base URL
repository.gatech.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Fahrbach, Matthew. Probabilistic techniques for analyzing sampling algorithms and the dynamics of lattice models. Doctoral thesis, Georgia Institute of Technology, 2019. http://hdl.handle.net/1853/62274