Swendsen-Wang algorithm on the mean-field Potts model
We study the $q$-state ferromagnetic Potts model on the $n$-vertex complete graph known as the mean-field (Curie-Weiss) model. We analyze the Swendsen-Wang algorithm which is a Markov chain that utilizes the random cluster representation for the ferromagnetic Potts model to recolor large sets of ver...
| Những tác giả chính: | , , |
|---|---|
| Định dạng: | Journal article |
| Được phát hành: |
Wiley
2018
|
| _version_ | 1826281359986917376 |
|---|---|
| author | Galanis, A Stefankovic, D Vigoda, E |
| author_facet | Galanis, A Stefankovic, D Vigoda, E |
| author_sort | Galanis, A |
| collection | OXFORD |
| description | We study the $q$-state ferromagnetic Potts model on the $n$-vertex complete graph known as the mean-field (Curie-Weiss) model. We analyze the Swendsen-Wang algorithm which is a Markov chain that utilizes the random cluster representation for the ferromagnetic Potts model to recolor large sets of vertices in one step and potentially overcomes obstacles that inhibit single-site Glauber dynamics. Long et al. studied the case $q=2$, the Swendsen-Wang algorithm for the mean-field ferromagnetic Ising model, and showed that the mixing time satisfies: (i) $\Theta(1)$ for $\beta<\beta_c, $(ii) $\Theta(n^{1/4})$for$\beta=\beta_c,$ (iii)$ \Theta(\log n)$ for $\beta>\beta_c,$ where $\beta_c $is the critical temperature for the ordered/disordered phase transition. In contrast, for $q\geq 3$ there are two critical temperatures $0<\beta_u<\beta_{rc} $that are relevant. We prove that the mixing time of the Swendsen-Wang algorithm for the ferromagnetic Potts model on the $n$-vertex complete graph satisfies: (i) $\Theta(1) $for$ \beta<\beta_u, $(ii) $\Theta(n^{1/3}) $for $\beta=\beta_u,$ (iii) $\exp(n^{\Omega(1)})$ for$ \beta_u<\beta<\beta_{rc}, $and (iv)$ \Theta(\log{n})$ for $\beta\geq\beta_{rc}$. These results complement refined results of Cuff et al. on the mixing time of the Glauber dynamics for the ferromagnetic Potts model. |
| first_indexed | 2024-03-07T00:27:41Z |
| format | Journal article |
| id | oxford-uuid:7eadf1a3-88e2-4f8c-b95e-03312d4dc63b |
| institution | University of Oxford |
| last_indexed | 2024-03-07T00:27:41Z |
| publishDate | 2018 |
| publisher | Wiley |
| record_format | dspace |
| spelling | oxford-uuid:7eadf1a3-88e2-4f8c-b95e-03312d4dc63b2022-03-26T21:11:45ZSwendsen-Wang algorithm on the mean-field Potts modelJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:7eadf1a3-88e2-4f8c-b95e-03312d4dc63bSymplectic Elements at OxfordWiley2018Galanis, AStefankovic, DVigoda, EWe study the $q$-state ferromagnetic Potts model on the $n$-vertex complete graph known as the mean-field (Curie-Weiss) model. We analyze the Swendsen-Wang algorithm which is a Markov chain that utilizes the random cluster representation for the ferromagnetic Potts model to recolor large sets of vertices in one step and potentially overcomes obstacles that inhibit single-site Glauber dynamics. Long et al. studied the case $q=2$, the Swendsen-Wang algorithm for the mean-field ferromagnetic Ising model, and showed that the mixing time satisfies: (i) $\Theta(1)$ for $\beta<\beta_c, $(ii) $\Theta(n^{1/4})$for$\beta=\beta_c,$ (iii)$ \Theta(\log n)$ for $\beta>\beta_c,$ where $\beta_c $is the critical temperature for the ordered/disordered phase transition. In contrast, for $q\geq 3$ there are two critical temperatures $0<\beta_u<\beta_{rc} $that are relevant. We prove that the mixing time of the Swendsen-Wang algorithm for the ferromagnetic Potts model on the $n$-vertex complete graph satisfies: (i) $\Theta(1) $for$ \beta<\beta_u, $(ii) $\Theta(n^{1/3}) $for $\beta=\beta_u,$ (iii) $\exp(n^{\Omega(1)})$ for$ \beta_u<\beta<\beta_{rc}, $and (iv)$ \Theta(\log{n})$ for $\beta\geq\beta_{rc}$. These results complement refined results of Cuff et al. on the mixing time of the Glauber dynamics for the ferromagnetic Potts model. |
| spellingShingle | Galanis, A Stefankovic, D Vigoda, E Swendsen-Wang algorithm on the mean-field Potts model |
| title | Swendsen-Wang algorithm on the mean-field Potts model |
| title_full | Swendsen-Wang algorithm on the mean-field Potts model |
| title_fullStr | Swendsen-Wang algorithm on the mean-field Potts model |
| title_full_unstemmed | Swendsen-Wang algorithm on the mean-field Potts model |
| title_short | Swendsen-Wang algorithm on the mean-field Potts model |
| title_sort | swendsen wang algorithm on the mean field potts model |
| work_keys_str_mv | AT galanisa swendsenwangalgorithmonthemeanfieldpottsmodel AT stefankovicd swendsenwangalgorithmonthemeanfieldpottsmodel AT vigodae swendsenwangalgorithmonthemeanfieldpottsmodel |