×

Exponentially slow mixing in the mean-field Swendsen-Wang dynamics. (English. French summary) Zbl 1434.60290

Summary: Swendsen-Wang dynamics for the Potts model was proposed in the late 1980’s as an alternative to single-site heat-bath dynamics, in which global updates allow this MCMC sampler to switch between metastable states and ideally mix faster. V. K. Gore and M. R. Jerrum [J. Stat. Phys. 97, No. 1–2, 67–86 (1999; Zbl 1006.82015)] found that this dynamics may in fact exhibit slow mixing: they showed that, for the Potts model with \(q\geq 3\) colors on the complete graph on \(n\) vertices at the critical point \(\beta_c(q)\), Swendsen-Wang dynamics has \(t_{\text{mix}}\geq \exp (c\sqrt{n})\). A. Galanis et al. [LIPIcs – Leibniz Int. Proc. Inform. 40, 815–828 (2015; Zbl 1375.82019)] showed that \(t_{\text{mix}}\geq \exp (cn^{1/3})\) throughout the critical window \((\beta_s,\beta_S)\) around \(\beta_c \), and A. Blanca and A. Sinclair [LIPIcs – Leibniz Int. Proc. Inform. 40, 528–543 (2015; Zbl 1375.60133)] established that \(t_{\text{mix}}\geq \exp (c\sqrt{n})\) in the critical window for the corresponding mean-field FK model, which implied the same bound for Swendsen-Wang via known comparison estimates. In both cases, an upper bound of \(t_{\text{mix}}\leq \exp (c'n)\) was known. Here we show that the mixing time is truly exponential in \(n\): namely, \(t_{\text{mix}}\geq \exp (cn)\) for Swendsen-Wang dynamics when \(q\geq 3\) and \(\beta \in (\beta_s,\beta_S)\), and the same bound holds for the related MCMC samplers for the mean-field FK model when \(q>2\).

MSC:

60K35 Interacting random processes; statistical mechanics type models; percolation theory
82B20 Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics
82B27 Critical phenomena in equilibrium statistical mechanics
82C20 Dynamic lattice systems (kinetic Ising, etc.) and systems on graphs in time-dependent statistical mechanics
05C80 Random graphs (graph-theoretic aspects)

References:

[1] A. Blanca and A. Sinclair. Dynamics for the mean-field random-cluster model. In Proc. of the 19th International Workshop on Randomization and Computation (RANDOM 2015) 528-543, 2015. · Zbl 1375.60133
[2] B. Bollobás. Random Graphs, 2nd edition. Cambridge Studies in Advanced Mathematics 73. Cambridge University Press, Cambridge, 2001.
[3] B. Bollobás, G. Grimmett and S. Janson. The random-cluster model on the complete graph. Probab. Theory Related Fields 104 (3) (1996) 283-317. · Zbl 0846.05075 · doi:10.1007/BF01213683
[4] C. Borgs, J. T. Chayes, A. Frieze, J. H. Kim, P. Tetali, E. Vigoda and V. H. Vu. Torpid mixing of some Monte Carlo Markov chain algorithms in statistical physics. In Proc. of the 40th Annual Symposium on Foundations of Computer Science (FOCS 1999) 218-229, 1999.
[5] C. Borgs, J. T. Chayes and P. Tetali. Tight bounds for mixing of the Swendsen-Wang algorithm at the Potts transition point. Probab. Theory Related Fields 152 (3-4) (2012) 509-557. · Zbl 1250.60034 · doi:10.1007/s00440-010-0329-0
[6] L. Chayes and J. Machta. Graphical representations and cluster algorithms I. Discrete spin systems. Phys. A 239 (4) (1997) 542-601.
[7] C. Cooper, M. E. Dyer, A. M. Frieze and R. Rue. Mixing properties of the Swendsen-Wang process on the complete graph and narrow grids. J. Math. Phys. 41 (3) (2000) 1499-1527. Probabilistic techniques in equilibrium and nonequilibrium statistical physics. · Zbl 1019.82011 · doi:10.1063/1.533194
[8] P. Cuff, J. Ding, O. Louidor, E. Lubetzky, Y. Peres and A. Sly. Glauber dynamics for the mean-field Potts model. J. Stat. Phys. 149 (3) (2012) 432-477. · Zbl 1254.82024 · doi:10.1007/s10955-012-0599-2
[9] R. G. Edwards and A. D. Sokal. Generalization of the Fortuin-Kasteleyn-Swendsen-Wang representation and Monte Carlo algorithm. Phys. Rev. D (3) 38 (6) (1988) 2009-2012.
[10] A. Galanis, D. Štefankovic and E. Vigoda. Swendsen-Wang algorithm on the mean-field Potts model. In Proc. of the 19th International Workshop on Randomization and Computation (RANDOM 2015) 815-828, 2015. · Zbl 1375.82019
[11] T. M. Garoni, G. Ossola, M. Polin and A. D. Sokal. Dynamic critical behavior of the Chayes-Machta algorithm for the random-cluster model, I. Two dimensions. J. Stat. Phys. 144 (3) (2011) 459-518. · Zbl 1227.82026 · doi:10.1007/s10955-011-0267-y
[12] R. Gheissari and E. Lubetzky. Mixing times of critical two-dimensional Potts models. Comm. Pure Appl. Math. 71 (5) (2018) 994-1046. · Zbl 1392.82007 · doi:10.1002/cpa.21718
[13] R. J. Glauber. Time-dependent statistics of the Ising model. J. Math. Phys. 4 (1963) 294-307. · Zbl 0145.24003 · doi:10.1063/1.1703954
[14] V. K. Gore and M. R. Jerrum. The Swendsen-Wang process does not always mix rapidly. J. Stat. Phys. 97 (1-2) (1999) 67-86. Extended version appeared in Proc. of the 29th Annual ACM Symposium on Theory of computing (STOC 1997), pages 674-681. · Zbl 0963.68216
[15] H. Guo and M. Jerrum. Random cluster dynamics for the Ising model is rapidly mixing. In Proc. of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2017) 1818-1827, 2017. · Zbl 1419.82013
[16] S. Janson, T. Luczak and A. Rucinski. Random Graphs. Wiley, 2000. · Zbl 0968.05003
[17] D. A. Levin, Y. Peres and E. L. Wilmer. Markov Chains and Mixing Times. American Mathematical Society, Providence, RI, 2009. With a chapter by James G. Propp and David B. Wilson. · Zbl 1160.60001
[18] Y. Long, A. Nachmias, W. Ning and Y. Peres. A power law of order \(1/4\) for critical mean field Swendsen-Wang dynamics. Mem. Amer. Math. Soc. 232 (1092) (2014) vi+84. · Zbl 1304.60078
[19] M. Luczak and T. Łuczak. The phase transition in the cluster-scaled model of a random graph. Random Structures Algorithms 28 (2) (2006) 215-246. · Zbl 1089.05066 · doi:10.1002/rsa.20088
[20] R. H. Swendsen and J.-S. Wang. Nonuniversal critical dynamics in Monte Carlo simulations. Phys. Rev. Lett. 58 (1987) 86-88.
[21] M. Ullrich. Comparison of Swendsen-Wang and heat-bath dynamics. Random Structures Algorithms 42 (4) (2013) 520-535. · Zbl 1272.82009 · doi:10.1002/rsa.20431
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.