Dynamics for the Potts and random-cluster models

Restricted (Penn State Only)
- Author:
- Zhang, Xusheng
- Graduate Program:
- Computer Science and Engineering
- Degree:
- Doctor of Philosophy
- Document Type:
- Dissertation
- Date of Defense:
- June 11, 2024
- Committee Members:
- Chitaranjan Das, Program Head/Chair
Martin Fürer, Major Field Member
Antonio Blanca, Chair & Dissertation Advisor
Chunhao Wang, Major Field Member
Alexei Novikov, Outside Unit & Field Member - Keywords:
- Markov chains
Random-cluster models
Mixing time
random graphs - Abstract:
- In this dissertation, I focus on sampling the Potts model and the random-cluster model. The Potts model, representing classical multi-spin systems in statistical physics, and the random-cluster model, a unifying edge model that extends edge percolation models, uniform spanning trees, and electric networks, are dual to each other. This duality allows them to be transformed into one another through a specific randomized operation. Sampling from these distributions is both algorithmically significant and technically challenging, with substantial implications for various applications. I primarily study a Markov-chain sampler for these models known as the Chayes-Machta dynamics, as well as its natural variant, the Swendsen-Wang dynamics, from a theoretical perspective. A key challenge in the research of Markov chains is determining their mixing time, which is the number of steps needed for the Markov chain to converge. First, we rigorously establish the mixing time of Chayes-Machta dynamics in the last remaining open case on the complete graph. Furthermore, in regimes where the Chayes-Machta dynamics exhibits exponentially large mixing times when starting from the worst-case initializations, we investigate the mixing time with random initializations and establish sharp conditions on the initialization necessary for fast mixing. Additionally, on general graphs, we improve the best known upper bounds on the mixing time for the Swendsen-Wang dynamics. The techniques developed in this work also yield mixing time results for other related Markov chains, including the mean-field Potts Glauber dynamics, Ising systematic scan dynamics, and more.