Phase transitions in spin systems: uniqueness, reconstruction and mixing time

Spin systems;Glauber dynamics;Markov chain;Mixing time;Uniqueness;Phase transitions

Yang, Linji ; Computer Science

University:Georgia Institute of Technology

Department:Computer Science

关键词: Spin systems;    Glauber dynamics;    Markov chain;    Mixing time;    Uniqueness;    Phase transitions;   

Others  :  https://smartech.gatech.edu/bitstream/1853/47593/1/yang_linji_201305_phd.pdf

美国|英语

来源: SMARTech Repository

【 摘 要 】

Spin systems are powerful mathematical models widely used and studied in Statistical Physics and Computer Science. This thesis focuses the study of spin systems on colorings and weighted independent sets (the hard-core model).In many spin systems, there exist phase transition phenomena: there is a threshold value of a parameter such that when the parameter is on one side of the threshold, the system exhibits the so-called spatial decay of correlation, i.e., the influence from a set of vertices to another set of vertices diminishes as the distance between the two sets grows; when the parameter is on the other side, long range correlations persist. The uniqueness problem and the reconstruction problem are two major threshold problems that are concerned with the decay of correlations in the Gibbs measure from different perspectives.In Computer Science, the study of spin systems mainly focused on finding an efficient algorithm that samples the configurations from a distribution that is very close to the Gibbs measure. Glauber dynamics is a typical Markov chain algorithm for performing sampling.In many systems, the convergence time of the Glauber dynamics also exhibits a threshold behavior: the speed of convergence experiences a dramatic change around the threshold of the parameter.The first two parts of this thesis focus on making connections between the phase transition of the convergence time of the dynamics and the phase transition of the reconstruction phenomenon in both colorings and the hard-core model on regular trees. A relatively sharp threshold is established for the change of the convergence time, which coincides with the reconstruction threshold. A general technique of upper bounding the conductance of the dynamics via analyzing the sensitivity of the reconstruction algorithm is proposed and proven to be very effective for lower bounding the convergence time of the dynamics.The third part of the thesis provides an innovative analytical method for establishing a strong version of the decay of correlation of the Gibbs distributions for many two spin systems on various classes of graphs. In particular, the method is applied to the hard-core model on the square lattice, a very important graph that is of great interest in both Statistical Physics and Computer Science. As a result, we significantly improve the lower bound of the uniqueness threshold on the square lattice and extend the range of parameter where the Glauber dynamics is rapidly mixing.