AMS Bookstore LOGO amslogo
Return to List

AMS TextbooksAMS Applications-related Books

A Power Law of Order 1/4 for Critical Mean Field Swendsen-Wang Dynamics
Yun Long, University of California, Berkeley, Asaf Nachmias, University of British Columbia, Vancouver, British Columbia, Canada, Weiyang Ning, University of Washington, Seattle, Washington, and Yuval Peres, Microsoft Research, Redmond, Washington
SEARCH THIS BOOK:

Memoirs of the American Mathematical Society
2014; 84 pp; softcover
Volume: 232
ISBN-10: 1-4704-0910-0
ISBN-13: 978-1-4704-0910-4
List Price: US$65
Individual Members: US$39
Institutional Members: US$52
Order Code: MEMO/232/1092
[Add Item]

Request Permissions

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 the authors show that the mixing time is \(\Theta(1)\) in high temperatures, \(\Theta(\log n)\) in low temperatures and \(\Theta(n^{1/4})\) at criticality. They 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.

Table of Contents

  • Introduction
  • Statement of the results
  • Mixing time preliminaries
  • Outline of the proof of Theorem 2.1
  • Random graph estimates
  • Supercritical case
  • Subcritical case
  • Critical Case
  • Fast mixing of the Swendsen-Wang process on trees
  • Acknowledgements
  • Bibliography
Powered by MathJax

  AMS Home | Comments: webmaster@ams.org
© Copyright 2014, American Mathematical Society
Privacy Statement

AMS Social

AMS and Social Media LinkedIn Facebook Podcasts Twitter YouTube RSS Feeds Blogs Wikipedia