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