×

A power law of order 1/4 for critical mean field Swendsen-Wang dynamics. (English) Zbl 1304.60078

Mem. Am. Math. Soc. 1092, v, 84 p. (2014).
Let a Swendsen-Wan Markov chain be given, defined on a complete graph on \(n\) vertices, and with percolation parametric \(cn^{-1}\), where \(c\) is a constant parameter independent of time. Then the mixing time of such a process is \(T=\Theta(\log\, n)\), when \(c>2\), \(T=\Theta {n^{1/4}}\), when \(c=2\), and \(T=\Theta (1)\), when \(c<2\). The proof of this result is lengthy and involves several estimates about percolation on a complete graph, and random graph estimates.

MSC:

60J10 Markov chains (discrete-time Markov processes on discrete state spaces)
82B20 Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] 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. · Zbl 1148.05001
[2] Krishna B. Athreya and Peter E. Ney, Branching processes, Springer-Verlag, New York-Heidelberg, 1972. Die Grundlehren der mathematischen Wissenschaften, Band 196. · Zbl 1070.60001
[3] Béla Bollobás, The evolution of random graphs, Trans. Amer. Math. Soc. 286 (1984), no. 1, 257-274. · Zbl 0579.05046 · doi:10.1090/S0002-9947-1984-0756039-5
[4] 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. · Zbl 1237.05192 · doi:10.1016/j.jctb.2011.04.003
[5] 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. · doi:10.1109/SFFCS.1999.814594
[6] 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). · Zbl 1321.68378
[7] 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. · Zbl 1019.82011 · doi:10.1063/1.533194
[8] 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). · Zbl 0945.82003 · doi:10.1002/(SICI)1098-2418(199910/12)15:3/4<242::AID-RSA4>3.3.CO;2-3
[9] Burgess Davis and David McDonald, An elementary proof of the local central limit theorem, J. Theoret. Probab. 8 (1995), no. 3, 693-701. · Zbl 0841.60013 · doi:10.1007/BF02218051
[10] Richard Durrett, Probability: theory and examples, 2nd ed., Duxbury Press, Belmont, CA, 1996. · Zbl 0709.60002
[11] 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. · doi:10.1103/PhysRevD.38.2009
[12] 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. · Zbl 0566.60097
[13] 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). · Zbl 0103.16301
[14] C. M. Fortuin and P. W. Kasteleyn, On the random-cluster model. I. Introduction and relation to other models, Physica 57 (1972), 536-564.
[15] 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 (electronic). · Zbl 0963.68216
[16] Svante Janson, Tomasz Łuczak, and Andrzej Rucinski, Random graphs, Wiley-Interscience Series in Discrete Mathematics and Optimization, Wiley-Interscience, New York, 2000. · Zbl 0968.05003
[17] Mark Jerrum and Alistair Sinclair, Polynomial-time approximation algorithms for the Ising model, SIAM J. Comput. 22 (1993), no. 5, 1087-1116. · Zbl 0782.05076 · doi:10.1137/0222066
[18] Richard M. Karp, The transitive closure of a random digraph, Random Structures Algorithms 1 (1990), no. 1, 73-93. · Zbl 0712.68076 · doi:10.1002/rsa.3240010106
[19] Gregory F. Lawler and Vlada Limic, Random walk: a modern introduction, Cambridge Studies in Advanced Mathematics, vol. 123, Cambridge University Press, Cambridge, 2010. · Zbl 1210.60002
[20] 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. · Zbl 1187.82076 · doi:10.1007/s00440-008-0189-z
[21] 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. · Zbl 1160.60001
[22] Tomasz Łuczak, Component behavior near the critical point of the random graph process, Random Structures Algorithms 1 (1990), no. 3, 287-310. · Zbl 0745.05048 · doi:10.1002/rsa.3240010305
[23] Anders Martin-Löf, Symmetric sampling procedures, general epidemic processes and their threshold limit theorems, J. Appl. Probab. 23 (1986), no. 2, 265-282. · Zbl 0605.92009
[24] 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. · Zbl 1130.05053
[25] Asaf Nachmias and Yuval Peres, The critical random graph, with martingales, Israel J. Math. 176 (2010), 29-41. · Zbl 1215.05168 · doi:10.1007/s11856-010-0019-8
[26] Asaf Nachmias and Yuval Peres, Critical percolation on random regular graphs, Random Structures Algorithms 36 (2010), no. 2, 111-148. · Zbl 1209.05228 · doi:10.1002/rsa.20277
[27] Persky N., Ben-Av R., Kanter I. and Domany E. (1996), Mean-field behavior of cluster dynamics, Phys. Rev. E 54, 2351-2358.
[28] Boris Pittel, On tree census and the giant component in sparse random graphs, Random Structures Algorithms 1 (1990), no. 3, 311-342. · Zbl 0747.05080 · doi:10.1002/rsa.3240010306
[29] Boris Pittel and Nicholas C. Wormald, Counting connected graphs inside-out, J. Combin. Theory Ser. B 93 (2005), no. 2, 127-172. · Zbl 1057.05044 · doi:10.1016/j.jctb.2004.09.005
[30] Ray T., Tamayo P. and Klein W. (1989), Mean-field study of the Swendsen-Wang dynamics. Phys. Rev. A 39, 5949-5953.
[31] 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). · Zbl 0971.68219
[32] 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. · Zbl 0937.82026 · doi:10.1007/BF02174209
[33] 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. · Zbl 0937.82028
[34] Frank Spitzer, A combinatorial lemma and its application to probability theory, Trans. Amer. Math. Soc. 82 (1956), 323-339. · Zbl 0071.13003 · doi:10.1090/S0002-9947-1956-0079851-X
[35] Swendsen R. H. and Wang J. S. (1987), Nonuniversal critical dynamics in Monte Carlo simulations. [[rm]]Phys. Rev. Lett. 58, 86-88.
[36] Wang J. S. (1990), Critical dynamics of the Swendsen-Wang algorithm in the three-dimensional Ising model. Physica A 164, 240-244.
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.