Spatial and temporal mixing of Gibbs measures [microform]
- Bib ID:
- 5036259
- Format:
- Book and Microform
- Author:
- Sly, Allan Murray
- Online Version:
- http://gateway.proquest.com/openurl?url_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:dissertation&res_dat=xri:pqdiss&rft_dat=xri:pqdiss:3383463
Broken link? let us search Trove , the Wayback Machine , or Google for you.
- Description:
- 204 p.
- ISBN:
- 9781109468007
- Summary:
-
In this thesis we address a number of questions on the temporal and spatial mixing of Gibbs measures. We show that in the Ising model with inverse temperature beta the Gibbs sampler mixes in time O( n log n) on any graph of maximum degree d and n vertices when (d -- 1) tanh beta < 1. The condition is tight as the mixing time is exponential in n on almost all random d-regular graphs when (d -- 1) tanh beta > 1. This is the first sufficient condition on mixing of Gibbs samplers which is both tight and holds for general graphs. We also analyze the Gibbs sampler on Erds̲-Rňyi random graphs G(n, d/n) for a number of models. For the Ising model we obtain tight results. For the colouring model we give the first proof that the Gibbs sampler mixes rapidly with a constant number of colours. Similar results are proven for the hardcore model and more general models with soft-constraints. We examine how spatial mixing thresholds are affected by the geometry of the graph.
We show that counter to the commonly held notion that trees are the extreme case for spatial mixing we provide an example of a Gibbs measure which has uniqueness on the d-regular tree but not on all d-regular graphs. In the second part of the thesis we look specifically at the reconstruction problem on the tree which has been studied in numerous contexts including statistical physics, information theory and computational biology. Rigorous reconstruction thresholds have only been established in a small number of models. We prove the first exact reconstruction threshold in a non-binary model establishing the Kesten-Stigum bound for the 3-state Potts model on regular trees of large degree. We further establish that the Kesten-Stigum bound is not tight for the q-state Potts model when q >= 5.
Moreover, we determine asymptotics for these reconstruction thresholds. In the special case of proper colourings, we give precise asymptotics on the reconstruction threshold in terms of the number of colours required.
- Notes:
-
- (UMI)AAI3383463
- Source: Dissertation Abstracts International, Volume: 70-11, Section: B, page: 6975.
- Adviser: Elchanan Mossel.
- Thesis (Ph.D.)--University of California, Berkeley, 2009.
- Reproduction:
- Microfiche. Ann Arbor, Mich. : University Microfilms International.
- Subject:
- Statistics
- Other authors/contributors:
- University of California, Berkeley
- Copyright:
-
In Copyright
Contact us for information about copying.
Copyright status was determined using the following information:
- Material type:
- Literary Dramatic Musical
- Published status:
- Unpublished
- Creation date:
- 2009
Copyright status may not be correct if data in the record is incomplete or inaccurate. Other access conditions may also apply. For more information please see: Copyright in library collections.
Request this item
Request this item to view in the Library’s reading room.