A power law of order 1/4 for critical mean field Swendsen-Wang dynamics / Yun Long [and three others].

Format:

• Book

Author/Creator:

• Long, Yun, 1982- author.

Series:

• Memoirs of the American Mathematical Society ; 0065-9266. Volume 232, Number 1092.
• Memoirs of the American Mathematical Society ; Volume 232, Number 1092

Language:

English

Subjects (All):

• Markov processes.
• Spin waves--Mathematical models.

Physical Description:

1 online resource (v, 84 pages).

Edition:

1st ed.

Place of Publication:

Providence, Rhode Island : American Mathematical Society, [2014]

Language Note:

English

Summary:

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.

Contents:

• Cover
• Title page
• Chapter 1. Introduction
• Chapter 2. Statement of the results
• 2.1. Random graph estimates
• Chapter 3. Mixing time preliminaries
• Chapter 4. Outline of the proof of Theorem 2.1
• 4.1. Outline of the Proof of Theorem 2.1 (i)
• 4.2. Outline of the Proof of Theorem 2.1 (iii)
• 4.3. Outline of the Proof of Theorem 2.1 (ii)
• Chapter 5. Random graph estimates
• 5.1. The exploration process
• 5.2. Random graph lemmas for non-critical cases
• 5.3. Random graph lemmas for the near-critical case
• Chapter 6. Supercritical case
• Chapter 7. Subcritical case
• Chapter 8. Critical Case
• 8.1. Starting at the [ ^{3/4}, ] regime: Proof of Theorem 8.1
• 8.2. Starting at the [0, ^{3/4}] regime: Proof of Theorem 8.2
• 8.3. The lower bound on the mixing time
• Chapter 9. Fast mixing of the Swendsen-Wang process on trees
• Acknowledgements
• Bibliography
• Back Cover.

Notes:

• "Volume 232, number 1092 (fourth of 6 numbers), November 2014."
• Includes bibliographical references.
• Description based on print version record.

ISBN:

1-4704-1895-9