Document Open Access Logo

Sampling from Potts on Random Graphs of Unbounded Degree via Random-Cluster Dynamics

Authors Antonio Blanca, Reza Gheissari

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2022.24.pdf
  • Filesize: 0.78 MB
  • 15 pages

Document Identifiers

Author Details

Antonio Blanca
  • Department of CSE, Pennsylvania State University, University Park, PA, USA
Reza Gheissari
  • Department of Statistics and EECS, University of California, Berkeley, CA, USA

Funding

  • Gheissari, Reza: Thanks the Miller Institute for Basic Research for its support.

Acknowledgements

The authors thank the anonymous referees for their helpful comments.

Cite AsGet BibTex

Antonio Blanca and Reza Gheissari. Sampling from Potts on Random Graphs of Unbounded Degree via Random-Cluster Dynamics. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 24:1-24:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2022.24

Abstract

We consider the problem of sampling from the ferromagnetic Potts and random-cluster models on a general family of random graphs via the Glauber dynamics for the random-cluster model. The random-cluster model is parametrized by an edge probability p ∈ (0,1) and a cluster weight q > 0. We establish that for every q ≥ 1, the random-cluster Glauber dynamics mixes in optimal Θ(nlog n) steps on n-vertex random graphs having a prescribed degree sequence with bounded average branching γ throughout the full high-temperature uniqueness regime p < p_u(q,γ). The family of random graph models we consider includes the Erdős-Rényi random graph G(n,γ/n), and so we provide the first polynomial-time sampling algorithm for the ferromagnetic Potts model on Erdős-Rényi random graphs for the full tree uniqueness regime. We accompany our results with mixing time lower bounds (exponential in the largest degree) for the Potts Glauber dynamics, in the same settings where our Θ(n log n) bounds for the random-cluster Glauber dynamics apply. This reveals a novel and significant computational advantage of random-cluster based algorithms for sampling from the Potts model at high temperatures.

Subject Classification

ACM Subject Classification
  • Theory of computation → Random walks and Markov chains
  • Theory of computation → Generating random combinatorial structures
  • Theory of computation → Random network models
  • Mathematics of computing → Probabilistic algorithms
  • Mathematics of computing → Markov processes
Keywords
  • Potts model
  • random-cluster model
  • random graphs
  • Markov chains
  • mixing time
  • tree uniqueness

Metrics

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

Related Versions

References

  1. Antonio Blanca, Zongchen Chen, Daniel Štefankovič, and Eric Vigoda. The Swendsen-Wang dynamics on trees. In Proceedings of the 25th International Workshop on Randomization and Computation (RANDOM), 2021. Google Scholar
  2. Antonio Blanca, Andreas Galanis, Leslie Ann Goldberg, Daniel Štefankovič, Eric Vigoda, and Kuan Yang. Sampling in uniqueness from the Potts and random-cluster models on random regular graphs. In Proceedings of the 22nd International Workshop on Randomization and Computation (RANDOM), 2018. Google Scholar
  3. Antonio Blanca and Reza Gheissari. Random-cluster dynamics on random regular graphs in tree uniqueness. Communications in Mathematical Physics, 2021. URL: https://doi.org/10.1007/s00220-021-04093-z.
  4. Antonio Blanca and Reza Gheissari. Sampling from Potts on random graphs of unbounded degree via random-cluster dynamics. arXiv preprint, 2021. URL: http://arxiv.org/abs/2107.10246.
  5. Antonio Blanca, Reza Gheissari, and Eric Vigoda. Random-cluster dynamics in ℤ²: Rapid mixing with general boundary conditions. Ann. Appl. Probab., 30(1):418-459, February 2020. URL: https://doi.org/10.1214/19-AAP1505.
  6. Antonio Blanca and Alistair Sinclair. Dynamics for the mean-field random-cluster model. In Proceedings of the 19th International Workshop on Randomization and Computation (RANDOM), pages 528-543, 2015. URL: https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2015.528.
  7. Antonio Blanca and Alistair Sinclair. Random-cluster dynamics in ℤ². Probab. Theory Related Fields, 2016. Extended abstract appeared in Proc. of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2016), pp. 498-513. URL: https://doi.org/10.1007/s00440-016-0725-1.
  8. Antonio Blanca, Alistair Sinclair, and Xusheng Zhang. The critical mean-field Chayes-Machta dynamics. In Proceedings of the 25th International Workshop on Randomization and Computation (RANDOM), 2021. Google Scholar
  9. Béla Bollobás. A probabilistic proof of an asymptotic formula for the number of labelled regular graphs. European Journal of Combinatorics, 1(4):311-316, 1980. Google Scholar
  10. Béla Bollobás. Random Graphs. Cambridge Studies in Advanced Mathematics. Cambridge University Press, 2 edition, 2001. URL: https://doi.org/10.1017/CBO9780511814068.
  11. Magnus Bordewich, Catherine Greenhill, and Viresh Patel. Mixing of the glauber dynamics for the ferromagnetic potts model. Random Structures & Algorithms, 48(1):21-52, 2016. Google Scholar
  12. Christian Borgs, Jennifer Chayes, Tyler Helmuth, Will Perkins, and Prasad Tetali. Efficient sampling and counting algorithms for the Potts model on Z^d at all temperatures. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, pages 738-751, New York, NY, USA, 2020. Association for Computing Machinery. URL: https://doi.org/10.1145/3357713.3384271.
  13. Christian Borgs, Jennifer T. Chayes, Alan Frieze, Jeong H. Kim, Prasad Tetali, Eric Vigoda, and Van 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), pages 218-229, 1999. URL: https://doi.org/10.1109/SFFCS.1999.814594.
  14. Christian Borgs, Jennifer T. Chayes, and Prasad Tetali. Tight bounds for mixing of the Swendsen-Wang algorithm at the Potts transition point. Probab. Theory Related Fields, 152(3-4):509-557, 2012. URL: https://doi.org/10.1007/s00440-010-0329-0.
  15. Lincoln Chayes and Jon Machta. Graphical representations and cluster algorithms I. Discrete spin systems. Physica A: Statistical Mechanics and its Applications, 239(4):542-601, 1997. Google Scholar
  16. Xiaoyu Chen, Weiming Feng, Yitong Yin, and Xinyuan Zhang. Rapid mixing of Glauber dynamics via spectral independence for all degrees. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 137-148. IEEE, 2022. Google Scholar
  17. Amin Coja-Oghlan, Andreas Galanis, Leslie Ann Goldberg, Jean Bernoulli Ravelomanana, Daniel Štefankovič, and Eric Vigoda. Metastability of the Potts Ferromagnet on Random Regular Graphs. In Mikołaj Bojańczyk, Emanuela Merelli, and David P. Woodruff, editors, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022), volume 229 of Leibniz International Proceedings in Informatics (LIPIcs), pages 45:1-45:20, Dagstuhl, Germany, 2022. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. URL: https://doi.org/10.4230/LIPIcs.ICALP.2022.45.
  18. Paul Cuff, Jian Ding, Oren Louidor, Eyal Lubetzky, Yuval Peres, and Allan Sly. Glauber dynamics for the mean-field Potts model. Journal of Statistical Physics, 149(3):432-477, 2012. Google Scholar
  19. Amir Dembo, Andrea Montanari, Allan Sly, and Nike Sun. The replica symmetric solution for Potts models on d-regular graphs. Communications in Mathematical Physics, 327(2):551-575, 2014. URL: https://doi.org/10.1007/s00220-014-1956-6.
  20. Martin Dyer, Abraham D Flaxman, Alan M Frieze, and Eric Vigoda. Randomly coloring sparse random graphs with fewer colors than the maximum degree. Random Structures & Algorithms, 29(4):450-465, 2006. Google Scholar
  21. Martin Dyer, Leslie Ann Goldberg, and Mark Jerrum. Dobrushin conditions and systematic scan. Combinatorics, Probability and Computing, 17(6):761-779, 2008. Google Scholar
  22. Martin Dyer, Leslie Ann Goldberg, and Mark Jerrum. Matrix norms and rapid mixing for spin systems. The Annals of Applied Probability, 19(1):71-107, 2009. Google Scholar
  23. Robert G. Edwards and Alan D. Sokal. Generalization of the Fortuin-Kasteleyn-Swendsen-Wang representation and Monte Carlo algorithm. Phys. Rev. D (3), 38(6):2009-2012, 1988. URL: https://doi.org/10.1103/PhysRevD.38.2009.
  24. G. Ellison. Learning, local interaction, and coordination. Econometrica: Journal of the Econometric Society, pages 1047-1071, 1993. Google Scholar
  25. J. Felsenstein. Inferring phylogenies, volume 2. Sinauer Associates, Inc., Sunderland, MA, 2004. Google Scholar
  26. Cornelius M. Fortuin and Pieter W. Kasteleyn. On the random-cluster model. I. Introduction and relation to other models. Physica, 57:536-564, 1972. Google Scholar
  27. Alan Frieze and Michał Karoński. Introduction to random graphs. Cambridge University Press, 2016. Google Scholar
  28. Andreas Galanis, Leslie Ann Goldberg, and James Stewart. Fast mixing via polymers for random graphs with unbounded degree. Information and Computation, page 104894, 2022. Google Scholar
  29. Andreas Galanis, Daniel Štefankovic, and Eric Vigoda. Swendsen-Wang Algorithm on the Mean-Field Potts Model. In Proc. of the 19th International Workshop on Randomization and Computation (RANDOM 2015), pages 815-828, 2015. URL: https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2015.815.
  30. Andreas Galanis, Daniel Štefankovič, Eric Vigoda, and Linji Yang. Ferromagnetic Potts model: Refined #BIS-hardness and related results. SIAM Journal on Computing, 45(6):2004-2065, 2016. Google Scholar
  31. Shirshendu Ganguly and Insuk Seo. Information percolation and cutoff for the random-cluster model. Random Structures & Algorithms, 57(3):770-822, 2020. URL: https://doi.org/10.1002/rsa.20931.
  32. S. Geman and C. Graffigne. Markov random field image models and their applications to computer vision. In Proceedings of the International Congress of Mathematicians, volume 1, pages 1496-1517. Berkeley, CA, 1986. Google Scholar
  33. H.-O. Georgii. Gibbs measures and phase transitions, volume 9. Walter de Gruyter, 2011. Google Scholar
  34. Reza Gheissari and Eyal Lubetzky. Mixing times of critical two-dimensional Potts models. Comm. Pure Appl. Math, 71(5):994-1046, 2018. Google Scholar
  35. Reza Gheissari and Eyal Lubetzky. Quasi-polynomial mixing of critical two-dimensional random cluster models. Random Structures and Algorithms, 2019. URL: https://doi.org/10.1002/rsa.20868.
  36. Reza Gheissari, Eyal Lubetzky, and Yuval Peres. Exponentially slow mixing in the mean-field Swendsen-Wang dynamics. Annales de l'Institut Henri Poincaré, Probabilités et Statistiques, 56(1):68-86, 2020. URL: https://doi.org/10.1214/18-AIHP955.
  37. Geoffrey Grimmett. The random-cluster model. In Probability on discrete structures, volume 110 of Encyclopaedia Math. Sci., pages 73-123. Springer, Berlin, 2004. URL: https://doi.org/10.1007/978-3-662-09444-0_2.
  38. Heng Guo and Mark Jerrum. Random cluster dynamics for the Ising model is rapidly mixing. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1818-1827, 2017. Google Scholar
  39. Olle Häggström. The random-cluster model on a homogeneous tree. Probability Theory and Related Fields, 104(2):231-253, 1996. URL: https://doi.org/10.1007/BF01247839.
  40. Matan Harel and Yinon Spinka. Finitary codings for the random-cluster model and other infinite-range monotone models. Electronic Journal of Probability, 27:1-32, 2022. Google Scholar
  41. Thomas P Hayes. A simple condition implying rapid mixing of single-site dynamics on spin systems. In Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 39-46. IEEE, 2006. Google Scholar
  42. Tyler Helmuth, Matthew Jenssen, and Will Perkins. Finite-size scaling, phase coexistence, and algorithms for the random cluster model on random graphs, 2020. URL: http://arxiv.org/abs/2006.11580.
  43. Jacob Holm, Kristian De Lichtenberg, and Mikkel Thorup. Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity. Journal of the ACM (JACM), 48(4):723-760, 2001. Google Scholar
  44. Johan 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
  45. Jeong Han Kim. Poisson cloning model for random graphs. In International Congress of Mathematicians (ICM), 2006. Google Scholar
  46. David A. Levin and Yuval Peres. Markov chains and mixing times (second edition). The Mathematical Intelligencer, 41(1):90-91, 2019. URL: https://doi.org/10.1007/s00283-018-9839-x.
  47. Yun Long, Asaf Nachmias, Weiyang Ning, and Yuval Peres. A power law of order 1/4 for critical mean field Swendsen-Wang dynamics. Mem. Amer. Math. Soc., 232(1092), 2014. URL: https://doi.org/10.1090/memo/1092.
  48. Russell Lyons. The Ising model and percolation on trees and tree-like graphs. Communications in Mathematical Physics, 125(2):337-353, 1989. URL: https://doi.org/cmp/1104179469.
  49. A. Montanari and A. Saberi. The spread of innovations in social networks. Proceedings of the National Academy of Sciences, 107(47):20196-20201, 2010. Google Scholar
  50. Elchanan Mossel and Allan Sly. Rapid mixing of Gibbs sampling on graphs that are sparse on average. Random Structures & Algorithms, 35(2):250-270, 2009. Google Scholar
  51. Elchanan Mossel and Allan Sly. Exact thresholds for Ising-Gibbs samplers on general graphs. Ann. Probab., 41(1):294-328, January 2013. URL: https://doi.org/10.1214/11-AOP737.
  52. S. Osindero and G.E. Hinton. Modeling image patches with a directed hierarchy of Markov random fields. In Advances in neural information processing systems, pages 1121-1128, 2008. Google Scholar
  53. Yuval Peres and Peter Winkler. Can extra updates delay mixing? Communications in Mathematical Physics, 323(3):1007-1016, 2013. URL: https://doi.org/10.1007/s00220-013-1776-0.
  54. S. Roth and M.J. Black. Fields of experts: A framework for learning image priors. In Proceedings of the 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR), volume 2, pages 860-867, 2005. Google Scholar
  55. Robert H. Swendsen and Jian-Sheng Wang. Nonuniversal critical dynamics in Monte Carlo simulations. Phys. Rev. Lett., 58:86-88, January 1987. URL: https://doi.org/10.1103/PhysRevLett.58.86.
  56. Mikkel Thorup. Near-optimal fully-dynamic graph connectivity. In Proceedings of the 32nd Annual ACM symposium on Theory of computing (STOC), pages 343-350, 2000. Google Scholar
  57. Mario Ullrich. Swendsen-Wang is faster than single-bond dynamics. SIAM Journal on Discrete Mathematics, 28(1):37-48, 2014. URL: https://doi.org/10.1137/120864003.
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 Imprint Privacy Contact