AMS eBook CollectionsOne of the world's most respected mathematical collections, available in digital format for your library or institution
A power law of order 1/4 for critical mean field Swendsen-Wang dynamics
About this Title
Yun Long, Asaf Nachmias, Weiyang Ning and Yuval Peres
Publication: Memoirs of the American Mathematical Society
Publication Year:
2014; Volume 232, Number 1092
ISBNs: 978-1-4704-0910-4 (print); 978-1-4704-1895-3 (online)
DOI: https://doi.org/10.1090/memo/1092
Published electronically: March 11, 2014
Keywords: Markov chains,
Mixing time,
Ising model,
Swendsen-Wang algorithm
MSC: Primary 60J10, 82B20
Table of Contents
Chapters
- 1. Introduction
- 2. Statement of the results
- 3. Mixing time preliminaries
- 4. Outline of the proof of Theorem
- 5. Random graph estimates
- 6. Supercritical case
- 7. Subcritical case
- 8. Critical Case
- 9. Fast mixing of the Swendsen-Wang process on trees
- Acknowledgements
Abstract
The Swendsen-Wang dynamics is a Markov chain widely used by physicists to sample from the Boltzmann-Gibbs distribution of the Ising model. Cooper, Dyer, Frieze and Rue proved that on the complete graph $K_n$ the mixing time of the chain is at most $O(\sqrt {n})$ for all non-critical temperatures. In this paper we show that the mixing time is $\Theta (1)$ in high temperatures, $\Theta (\log n)$ in low temperatures and $\Theta (n^{1/4})$ at criticality. We also provide an upper bound of $O(\log n)$ for Swendsen-Wang dynamics for the $q$-state ferromagnetic Potts model on any tree of $n$ vertices.- Noga Alon and Joel H. Spencer, The probabilistic method, 3rd ed., Wiley-Interscience Series in Discrete Mathematics and Optimization, John Wiley & Sons, Inc., Hoboken, NJ, 2008. With an appendix on the life and work of Paul Erdős. MR 2437651
- Krishna B. Athreya and Peter E. Ney, Branching processes, Springer-Verlag, New York-Heidelberg, 1972. Die Grundlehren der mathematischen Wissenschaften, Band 196. MR 0373040
- Béla Bollobás, The evolution of random graphs, Trans. Amer. Math. Soc. 286 (1984), no. 1, 257–274. MR 756039, DOI 10.1090/S0002-9947-1984-0756039-5
- Béla Bollobás and Oliver Riordan, Asymptotic normality of the size of the giant component via a random walk, J. Combin. Theory Ser. B 102 (2012), no. 1, 53–61. MR 2871766, DOI 10.1016/j.jctb.2011.04.003
- Christian Borgs, Jennifer T. Chayes, Alan Frieze, Jeong Han Kim, Prasad Tetali, Eric Vigoda, and Van Ha Vu, Torpid mixing of some Monte Carlo Markov chain algorithms in statistical physics, 40th Annual Symposium on Foundations of Computer Science (New York, 1999) IEEE Computer Soc., Los Alamitos, CA, 1999, pp. 218–229. MR 1917562, DOI 10.1109/SFFCS.1999.814594
- Bubley R. and Dyer M. (1997), Path Coupling: A technique for proving rapid mixing in Markov chains. Proceeding of the 38th Annual Symposium FOCS (IEEE).
- Colin Cooper, Martin E. Dyer, Alan M. Frieze, and Rachel Rue, Mixing properties of the Swendsen-Wang process on the complete graph and narrow grids, J. Math. Phys. 41 (2000), no. 3, 1499–1527. Probabilistic techniques in equilibrium and nonequilibrium statistical physics. MR 1757967, DOI 10.1063/1.533194
- Colin Cooper and Alan M. Frieze, Mixing properties of the Swendsen-Wang process on classes of graphs, Random Structures Algorithms 15 (1999), no. 3-4, 242–261. Statistical physics methods in discrete probability, combinatorics, and theoretical computer science (Princeton, NJ, 1997). MR 1716764, DOI 10.1002/(SICI)1098-2418(199910/12)15:3/4<242::AID-RSA4>3.3.CO;2-3
- Burgess Davis and David McDonald, An elementary proof of the local central limit theorem, J. Theoret. Probab. 8 (1995), no. 3, 693–701. MR 1340834, DOI 10.1007/BF02218051
- Richard Durrett, Probability: theory and examples, 2nd ed., Duxbury Press, Belmont, CA, 1996. MR 1609153
- Robert G. Edwards and Alan D. Sokal, Generalization of the Fortuin-Kasteleyn-Swendsen-Wang representation and Monte Carlo algorithm, Phys. Rev. D (3) 38 (1988), no. 6, 2009–2012. MR 965465, DOI 10.1103/PhysRevD.38.2009
- Richard S. Ellis, Entropy, large deviations, and statistical mechanics, Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 271, Springer-Verlag, New York, 1985. MR 793553
- P. Erdős and A. Rényi, On the evolution of random graphs, Magyar Tud. Akad. Mat. Kutató Int. Közl. 5 (1960), 17–61 (English, with Russian summary). MR 125031
- C. M. Fortuin and P. W. Kasteleyn, On the random-cluster model. I. Introduction and relation to other models, Physica 57 (1972), 536–564. MR 359655
- Vivek K. Gore and Mark R. Jerrum, The Swendsen-Wang process does not always mix rapidly, STOC ’97 (El Paso, TX), ACM, New York, 1999, pp. 674–681. MR 1753371
- Svante Janson, Tomasz Łuczak, and Andrzej Rucinski, Random graphs, Wiley-Interscience Series in Discrete Mathematics and Optimization, Wiley-Interscience, New York, 2000. MR 1782847
- Mark Jerrum and Alistair Sinclair, Polynomial-time approximation algorithms for the Ising model, SIAM J. Comput. 22 (1993), no. 5, 1087–1116. MR 1237164, DOI 10.1137/0222066
- Richard M. Karp, The transitive closure of a random digraph, Random Structures Algorithms 1 (1990), no. 1, 73–93. MR 1068492, DOI 10.1002/rsa.3240010106
- Gregory F. Lawler and Vlada Limic, Random walk: a modern introduction, Cambridge Studies in Advanced Mathematics, vol. 123, Cambridge University Press, Cambridge, 2010. MR 2677157
- David A. Levin, Malwina J. Luczak, and Yuval Peres, Glauber dynamics for the mean-field Ising model: cut-off, critical power law, and metastability, Probab. Theory Related Fields 146 (2010), no. 1-2, 223–265. MR 2550363, DOI 10.1007/s00440-008-0189-z
- David A. Levin, Yuval Peres, and Elizabeth L. Wilmer, Markov chains and mixing times, American Mathematical Society, Providence, RI, 2009. With a chapter by James G. Propp and David B. Wilson. MR 2466937
- Tomasz Łuczak, Component behavior near the critical point of the random graph process, Random Structures Algorithms 1 (1990), no. 3, 287–310. MR 1099794, DOI 10.1002/rsa.3240010305
- Anders Martin-Löf, Symmetric sampling procedures, general epidemic processes and their threshold limit theorems, J. Appl. Probab. 23 (1986), no. 2, 265–282. MR 839984, DOI 10.1017/s0021900200029594
- Asaf Nachmias and Yuval Peres, Component sizes of the random graph outside the scaling window, ALEA Lat. Am. J. Probab. Math. Stat. 3 (2007), 133–142. MR 2349805
- Asaf Nachmias and Yuval Peres, The critical random graph, with martingales, Israel J. Math. 176 (2010), 29–41. MR 2653185, DOI 10.1007/s11856-010-0019-8
- Asaf Nachmias and Yuval Peres, Critical percolation on random regular graphs, Random Structures Algorithms 36 (2010), no. 2, 111–148. MR 2583058, DOI 10.1002/rsa.20277
- Persky N., Ben-Av R., Kanter I. and Domany E. (1996), Mean-field behavior of cluster dynamics, Phys. Rev. E 54, 2351-2358.
- Boris Pittel, On tree census and the giant component in sparse random graphs, Random Structures Algorithms 1 (1990), no. 3, 311–342. MR 1099795, DOI 10.1002/rsa.3240010306
- Boris Pittel and Nicholas C. Wormald, Counting connected graphs inside-out, J. Combin. Theory Ser. B 93 (2005), no. 2, 127–172. MR 2117934, DOI 10.1016/j.jctb.2004.09.005
- Ray T., Tamayo P. and Klein W. (1989), Mean-field study of the Swendsen-Wang dynamics. Phys. Rev. A 39, 5949-5953.
- J. Salas, Dynamic critical behavior of cluster algorithms for 2D Ashkin-Teller and Potts models, Markov Process. Related Fields 7 (2001), no. 1, 55–74. Inhomogeneous random systems (Cergy-Pontoise, 2000). MR 1835747
- Jesús Salas and Alan D. Sokal, Dynamic critical behavior of a Swendsen-Wang-type algorithm for the Ashkin-Teller model, J. Statist. Phys. 85 (1996), no. 3-4, 297–361. MR 1413666, DOI 10.1007/BF02174209
- Salas J. and Sokal A. D. (1997), Dynamic critical behavior of the Swendsen-Wang algorithm: the two-dimensional three-state Potts model revisited. J. Stat. Phys. 87 1-36.
- Frank Spitzer, A combinatorial lemma and its application to probability theory, Trans. Amer. Math. Soc. 82 (1956), 323–339. MR 79851, DOI 10.1090/S0002-9947-1956-0079851-X
- Swendsen R. H. and Wang J. S. (1987), Nonuniversal critical dynamics in Monte Carlo simulations. Phys. Rev. Lett. 58, 86-88.
- Wang J. S. (1990), Critical dynamics of the Swendsen-Wang algorithm in the three-dimensional Ising model. Physica A 164, 240-244.