• Login
    View Item 
    •   SMARTech Home
    • Georgia Tech Theses and Dissertations
    • Georgia Tech Theses and Dissertations
    • View Item
    •   SMARTech Home
    • Georgia Tech Theses and Dissertations
    • Georgia Tech Theses and Dissertations
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

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

    Thumbnail
    View/Open
    FAHRBACH-DISSERTATION-2019.pdf (7.693Mb)
    Date
    2019-11-11
    Author
    Fahrbach, Matthew
    Metadata
    Show full item record
    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.
    URI
    http://hdl.handle.net/1853/62274
    Collections
    • College of Computing Theses and Dissertations [1191]
    • Georgia Tech Theses and Dissertations [23877]

    Browse

    All of SMARTechCommunities & CollectionsDatesAuthorsTitlesSubjectsTypesThis CollectionDatesAuthorsTitlesSubjectsTypes

    My SMARTech

    Login

    Statistics

    View Usage StatisticsView Google Analytics Statistics
    facebook instagram twitter youtube
    • My Account
    • Contact us
    • Directory
    • Campus Map
    • Support/Give
    • Library Accessibility
      • About SMARTech
      • SMARTech Terms of Use
    Georgia Tech Library266 4th Street NW, Atlanta, GA 30332
    404.894.4500
    • Emergency Information
    • Legal and Privacy Information
    • Human Trafficking Notice
    • Accessibility
    • Accountability
    • Accreditation
    • Employment
    © 2020 Georgia Institute of Technology