Document Open Access Logo

The Swendsen-Wang Dynamics on Trees

Authors Antonio Blanca, Zongchen Chen, Daniel Štefankovič, Eric Vigoda

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2021.43.pdf
  • Filesize: 0.74 MB
  • 15 pages

Document Identifiers

Author Details

Antonio Blanca
  • Pennsylvania State University, University Park, PA, USA
Zongchen Chen
  • Georgia Institute of Technology, Atlanta, GA, USA
Daniel Štefankovič
  • University of Rochester, NY, USA
Eric Vigoda
  • Georgia Institute of Technology, Atlanta, GA, USA

Funding

  • Blanca, Antonio: Research supported in part by NSF grant CCF-1850443.
  • Chen, Zongchen: Research supported in part by NSF grant CCF-2007022.
  • Štefankovič, Daniel: Research supported in part by NSF grant CCF-2007287.
  • Vigoda, Eric: Research supported in part by NSF grant CCF-2007022.

Cite As Get BibTex

Antonio Blanca, Zongchen Chen, Daniel Štefankovič, and Eric Vigoda. The Swendsen-Wang Dynamics on Trees. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 207, pp. 43:1-43:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2021.43

Abstract

The Swendsen-Wang algorithm is a sophisticated, widely-used Markov chain for sampling from the Gibbs distribution for the ferromagnetic Ising and Potts models. This chain has proved difficult to analyze, due in part to the global nature of its updates. We present optimal bounds on the convergence rate of the Swendsen-Wang algorithm for the complete d-ary tree. Our bounds extend to the non-uniqueness region and apply to all boundary conditions. We show that the spatial mixing conditions known as Variance Mixing and Entropy Mixing, introduced in the study of local Markov chains by Martinelli et al. (2003), imply Ω(1) spectral gap and O(log n) mixing time, respectively, for the Swendsen-Wang dynamics on the d-ary tree. We also show that these bounds are asymptotically optimal. As a consequence, we establish Θ(log n) mixing for the Swendsen-Wang dynamics for all boundary conditions throughout the tree uniqueness region; in fact, our bounds hold beyond the uniqueness threshold for the Ising model, and for the q-state Potts model when q is small with respect to d. Our proofs feature a novel spectral view of the Variance Mixing condition inspired by several recent rapid mixing results on high-dimensional expanders and utilize recent work on block factorization of entropy under spatial mixing conditions.

Subject Classification

ACM Subject Classification
  • Theory of computation → Random walks and Markov chains
  • Mathematics of computing → Markov processes
  • Theory of computation → Design and analysis of algorithms
Keywords
  • Markov Chains
  • mixing times
  • Ising and Potts models
  • Swendsen-Wang dynamics
  • trees

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Blanca A., Chen Z., Štefankovič D., and Vigoda E. The Swendsen-Wang dynamics on trees. arXiv preprint arXiv:2007.08068, 2020. Google Scholar
  2. V. L. Alev and L. C. Lau. Improved analysis of higher order random walks and applications. In Proceedings of the 61st Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2020. Google Scholar
  3. N. Anari, K. Liu, and S. Oveis Gharan. Spectral independence in high-dimensional expanders and applications to the hardcore model. In Proceedings of the 52nd Annual ACM Symposium on Theory of Computing (STOC), 2020. Google Scholar
  4. B. Awerbuch and Y. Shiloach. New connectivity and MSF algorithms for shuffle-exchange network and PRAM. IEEE Computer Architecture Letters, 36(10):1258-1263, 1987. Google Scholar
  5. V. Beffara and H. Duminil-Copin. The self-dual point of the two-dimensional random-cluster model is critical for q ≥ 1. Probability Theory and Related Fields, 153:511-542, 2012. Google Scholar
  6. N. Berger, C. Kenyon, E. Mossel, and Y. Peres. Glauber dynamics on trees and hyperbolic graphs. Probability Theory and Related Fields, 131(3):311-340, 2005. Google Scholar
  7. H. A. Bethe. Statistical theory of superlattices. Proceedings of the Royal Society of London. Series A, Mathematical and Physical Sciences, 150(871):552-575, 1935. Google Scholar
  8. A. Blanca, P. Caputo, D. Parisi, A. Sinclair, and E. Vigoda. Entropy decay in the Swendsen-Wang dynamics on ℤ^d. In Proceedings of the 53st Annual ACM Symposium on Theory of Computing (STOC), page 1551–1564, 2021. Google Scholar
  9. A. Blanca, P. Caputo, A. Sinclair, and E. Vigoda. Spatial Mixing and Non-local Markov chains. In Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1965-1980, 2018. Google Scholar
  10. A. Blanca, A. Galanis, L. A. Goldberg, D. Štefankovič, E. Vigoda, and K. Yang. Sampling in uniqueness from the Potts and random-cluster models on random regular graphs. SIAM Journal on Discrete Mathematics, 34(1):742-793, 2020. Google Scholar
  11. A. Blanca, R. Gheissari, and E. Vigoda. Random-cluster dynamics in ℤ²: Rapid mixing with general boundary conditions. Annals of Applied Probability, 30(1):418-459, 2020. Google Scholar
  12. A. Blanca and A. Sinclair. Dynamics for the mean-field random-cluster model. Proceedings of the 19th International Workshop on Randomization and Computation, pages 528-543, 2015. Google Scholar
  13. M. Bordewich, C. Greenhill, and V. Patel. Mixing of the Glauber dynamics for the ferromagnetic Potts model. Random Structures & Algorithms, 48(1):21-52, 2016. Google Scholar
  14. P. Caputo and D. Parisi. Block factorization of the relative entropy via spatial mixing, 2020. URL: https://arxiv.org/abs/2004.10574.
  15. F. Cesi. Quasi-factorization of the entropy and logarithmic Sobolev inequalities for gibbs random fields. Probability Theory and Related Fields, 120(4):569-584, 2001. Google Scholar
  16. C. Cooper and A. M. Frieze. Mixing properties of the Swendsen-Wang process on classes of graphs. Random Structures and Algorithms, 15(3-4):242-261, 1999. Google Scholar
  17. M. Costeniuc, R. S. Ellis, and H. Touchette. Complete analysis of phase transitions and ensemble equivalence for the Curie-Weiss-Potts model. Journal of Mathematical Physics, 46(6):063301, 2005. Google Scholar
  18. P. Cuff, J. Ding, O. Louidor, E. Lubetzky, Y. Peres, and A. Sly. Glauber dynamics for the mean-field Potts model. Journal of Statistical Physics, 149(3):432-477, 2012. Google Scholar
  19. P. Diaconis and L. Saloff-Coste. Logarithmic Sobolev inequalities for finite Markov chains. Annals of Applied Probability, 6(3):695-750, 1996. Google Scholar
  20. H. Duminil-Copin, M. Gagnebin, M. Harel, I. Manolescu, and V. Tassion. Discontinuity of the phase transition for the planar random-cluster and Potts models with q > 4. Annales de l'ENS, 2016. Google Scholar
  21. H. Duminil-Copin, V. Sidoravicius, and V. Tassion. Continuity of the Phase Transition for Planar Random-Cluster and Potts Models with 1 ≤ q ≤ 4. Communications in Mathematical Physics, 349(1):47-107, 2017. Google Scholar
  22. M. Dyer, A. Sinclair, E. Vigoda, and D. Weitz. Mixing in time and space for lattice spin systems: A combinatorial view. Random Structure & Algorithms, 24(4):461-479, 2004. Google Scholar
  23. R. G. Edwards and A. D. Sokal. Generalization of the Fortuin-Kasteleyn-Swendsen-Wang representation and Monte Carlo algorithm. Physical Review D, 38(6):2009-2012, 1988. Google Scholar
  24. Grimmett G. The random-cluster model. In Probability on discrete structures, pages 73-123. Springer, 2004. Google Scholar
  25. A. Galanis, D. Štefankovič, and E. Vigoda. Swendsen-Wang algorithm on the mean-field Potts model. In Proceedings of the 19th International Workshop on Randomization and Computation, pages 815-828, 2015. Google Scholar
  26. A. Galanis, D. Štefankovič, E. Vigoda, and L. Yang. Ferromagnetic Potts model: Refined #BIS-hardness and related results. SIAM Journal on Computing, 45(6):2004-2065, 2016. Google Scholar
  27. H. O. Georgii. Gibbs Measures and Phase Transitions. De Gruyter Studies in Mathematics. Walter de Gruyter Inc, 1988. Google Scholar
  28. A. Gerschenfeld and A. Montanari. Reconstruction for models on random graphs. In Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 194-204, 2007. Google Scholar
  29. R. Gheissari, E. Lubetzky, and Y. Peres. Exponentially slow mixing in the mean-field Swendsen-Wang dynamics. In Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1981-1988, 2018. Google Scholar
  30. D. Gillman. A Chernoff bound for random walks on expander graphs. SIAM Journal on Computing, 27(4):1203-1220, 1998. Google Scholar
  31. O. Häggström. The random-cluster model on a homogeneous tree. Probability Theory and Related Fields, 104:231-253, 1996. Google Scholar
  32. T. P. Hayes and A. Sinclair. A general lower bound for mixing of single-site dynamics on graphs. In Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 511-520, 2005. Google Scholar
  33. M. Huber. A bounding chain for Swendsen-Wang. Random Structures & Algorithms, 22(1):43-59, 2003. Google Scholar
  34. M. Jerrum. Counting, sampling and integrating: algorithms and complexity. Lectures in Mathematics, Birkhäuser Verlag, 2003. Google Scholar
  35. M. Jerrum, A. Sinclair, and E. Vigoda. A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries. Journal of the ACM, 51(4):671-697, 2004. Google Scholar
  36. J. Jonasson. The random cluster model on a general graph and a phase transition characterization of nonamenability. Stochastic Processes and their Applications, 79(2):335-354, 1999. Google Scholar
  37. R. Kannan, L. Lovász, and M. Simonovits. Random walks and an O^*(n⁵) volume algorithm for convex bodies. Random structures and algorithms, 11(1):1-50, 1997. Google Scholar
  38. D. A. Levin, Y. Peres, and E. L. Wilmer. Markov Chains and Mixing Times. American Mathematical Society, 2008. Google Scholar
  39. F. Martinelli and E. Olivieri. Approach to equilibrium of Glauber dynamics in the one phase region. Communications in Mathematical Physics, 161(3):447-486, 1994. Google Scholar
  40. F. Martinelli, A. Sinclair, and D. Weitz. The Ising model on trees: Boundary conditions and mixing time. In Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 628-639, 2003. Google Scholar
  41. F. Martinelli, A. Sinclair, and D. Weitz. Fast mixing for independent sets. In Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 449-458. colorings and other model on trees. In, 2004. Google Scholar
  42. F. Martinelli and F. L. Toninelli. On the mixing time of the 2D stochastic Ising model with "plus" boundary conditions at low temperature. Communications in Mathematical Physics, 296(1):175-213, 2010. Google Scholar
  43. E. Mossel and Y. Peres. Information flow on trees. Annals of Applied Probability, 13(3):817-844, 2003. Google Scholar
  44. E. Mossel and A. Sly. Exact thresholds for Ising-Gibbs samplers on general graphs. The Annals of Probability, 41(1):294-328, 2013. Google Scholar
  45. R. Restrepo, D. Štefankovič, C. Vera, E. Vigoda, and L. Yang. Phase transition for Glauber dynamics for independent sets on regular trees. SIAM Journal on Discrete Mathematics, 28(2):835-861, 2014. Google Scholar
  46. L. Saloff-Coste. Lectures on finite Markov chains. In Lectures on probability theory and statistics, pages 301-413. 1997. Google Scholar
  47. A. Sly. Reconstruction for the Potts model. The Annals of Probability, 39(4):1365-1406, 2011. Google Scholar
  48. A. Sly and Y. Zhang. The Glauber dynamics of colorings on trees is rapidly mixing throughout the nonreconstruction regime. The Annals of Applied Probability, 27(5):2646-2674, 2017. Google Scholar
  49. R. H. Swendsen and J. S. Wang. Nonuniversal critical dynamics in Monte Carlo simulations. Physical Review Letters, 58:86-88, 1987. Google Scholar
  50. M. Ullrich. Rapid mixing of Swendsen-Wang and single-bond dynamics in two dimensions. Dissertationes Mathematicae, 502:64, 2014. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact