Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2507.20482 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908588615663616 |
|---|---|
| author | Blanca, Antonio Song, Zhezheng |
| author_facet | Blanca, Antonio Song, Zhezheng |
| contents | We study the speed of convergence of the Swendsen-Wang (SW) dynamics for the $q$-state ferromagnetic Potts model on the $n$-vertex complete graph, known as the mean-field model. The SW dynamics was introduced as an attractive alternative to the local Glauber dynamics, often offering faster convergence rates to stationarity in a variety of settings. A series of works have characterized the asymptotic behavior of the speed of convergence of the mean-field SW dynamics for all $q \ge 2$ and all values of the inverse temperature parameter $β> 0$. In particular, it is known that when $β> q$ the mixing time of the SW dynamics is $Θ(\log n)$. We strengthen this result by showing that for all $β> q$, there exists a constant $c(β,q) > 0$ such that the mixing time of the SW dynamics is $c(β,q) \log n + Θ(1)$. This implies that the mean-field SW dynamics exhibits the cutoff phenomenon in this temperature regime, demonstrating that this Markov chain undergoes a sharp transition from ''far from stationarity'' to ''well-mixed'' within a narrow $Θ(1)$ time window. The presence of cutoff is algorithmically significant, as simulating the chain for fewer steps than its mixing time could lead to highly biased samples. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_20482 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Cutoff for the Swendsen-Wang dynamics on the complete graph Blanca, Antonio Song, Zhezheng Probability We study the speed of convergence of the Swendsen-Wang (SW) dynamics for the $q$-state ferromagnetic Potts model on the $n$-vertex complete graph, known as the mean-field model. The SW dynamics was introduced as an attractive alternative to the local Glauber dynamics, often offering faster convergence rates to stationarity in a variety of settings. A series of works have characterized the asymptotic behavior of the speed of convergence of the mean-field SW dynamics for all $q \ge 2$ and all values of the inverse temperature parameter $β> 0$. In particular, it is known that when $β> q$ the mixing time of the SW dynamics is $Θ(\log n)$. We strengthen this result by showing that for all $β> q$, there exists a constant $c(β,q) > 0$ such that the mixing time of the SW dynamics is $c(β,q) \log n + Θ(1)$. This implies that the mean-field SW dynamics exhibits the cutoff phenomenon in this temperature regime, demonstrating that this Markov chain undergoes a sharp transition from ''far from stationarity'' to ''well-mixed'' within a narrow $Θ(1)$ time window. The presence of cutoff is algorithmically significant, as simulating the chain for fewer steps than its mixing time could lead to highly biased samples. |
| title | Cutoff for the Swendsen-Wang dynamics on the complete graph |
| topic | Probability |
| url | https://arxiv.org/abs/2507.20482 |