Planting and MCMC Sampling from the Potts model
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866908832594132992 |
|---|---|
| author | Galanis, Andreas Goldberg, Leslie Ann Smolarova, Paulina |
| author_facet | Galanis, Andreas Goldberg, Leslie Ann Smolarova, Paulina |
| contents | We consider the problem of sampling from the ferromagnetic $q$-state Potts model on the random $d$-regular graph with parameter $β>0$. A key difficulty that arises in sampling from the model is the existence of a metastability window $(β_u,β_u')$ where the distribution has two competing modes, the so-called disordered and ordered phases, causing MCMC-based algorithms to be slow mixing from worst-case initialisations.
To this end, Helmuth, Jenssen and Perkins designed a sampling algorithm that works for all $β$ when $q$ is large, using cluster expansion methods; more recently, their analysis technique has been adapted to show that random-cluster dynamics mixes fast when initialised more judiciously. However, a bottleneck behind cluster-expansion arguments is that they inherently only work for large $q$, whereas it is widely conjectured that sampling is possible for all $q,d\geq 3$. The only result so far that applies to general $q,d\geq 3$ is by Blanca and Gheissari who showed that the random-cluster dynamics mixes fast for $β<β_u$. For $β>β_u$, certain correlation phenomena emerge because of the metastability which have been hard to handle, especially for small $q$ and $d$.
Our main contribution is to perform a delicate analysis of the Potts distribution and the random-cluster dynamics that goes beyond the threshold $β_u$. We use planting as the main tool in our proofs, and combine it with the analysis of random-cluster dynamics. We are thus able to show that the random-cluster dynamics initialised from all-out mixes fast for all integers $q,d\geq 3$ beyond the uniqueness threshold $β_u$; our analysis works all the way up to the threshold $β_c\in (β_u,β_u')$ where the dominant mode switches from disordered to ordered. We also obtain an algorithm in the ordered regime $β>β_c$ that refines significantly the range of $q,d$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_14409 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Planting and MCMC Sampling from the Potts model Galanis, Andreas Goldberg, Leslie Ann Smolarova, Paulina Probability Discrete Mathematics 60J10, 68Q87, 68Q25 G.3; G.2 We consider the problem of sampling from the ferromagnetic $q$-state Potts model on the random $d$-regular graph with parameter $β>0$. A key difficulty that arises in sampling from the model is the existence of a metastability window $(β_u,β_u')$ where the distribution has two competing modes, the so-called disordered and ordered phases, causing MCMC-based algorithms to be slow mixing from worst-case initialisations. To this end, Helmuth, Jenssen and Perkins designed a sampling algorithm that works for all $β$ when $q$ is large, using cluster expansion methods; more recently, their analysis technique has been adapted to show that random-cluster dynamics mixes fast when initialised more judiciously. However, a bottleneck behind cluster-expansion arguments is that they inherently only work for large $q$, whereas it is widely conjectured that sampling is possible for all $q,d\geq 3$. The only result so far that applies to general $q,d\geq 3$ is by Blanca and Gheissari who showed that the random-cluster dynamics mixes fast for $β<β_u$. For $β>β_u$, certain correlation phenomena emerge because of the metastability which have been hard to handle, especially for small $q$ and $d$. Our main contribution is to perform a delicate analysis of the Potts distribution and the random-cluster dynamics that goes beyond the threshold $β_u$. We use planting as the main tool in our proofs, and combine it with the analysis of random-cluster dynamics. We are thus able to show that the random-cluster dynamics initialised from all-out mixes fast for all integers $q,d\geq 3$ beyond the uniqueness threshold $β_u$; our analysis works all the way up to the threshold $β_c\in (β_u,β_u')$ where the dominant mode switches from disordered to ordered. We also obtain an algorithm in the ordered regime $β>β_c$ that refines significantly the range of $q,d$. |
| title | Planting and MCMC Sampling from the Potts model |
| topic | Probability Discrete Mathematics 60J10, 68Q87, 68Q25 G.3; G.2 |
| url | https://arxiv.org/abs/2410.14409 |