Mixing time for the Ising model and random walks

In this thesis we study the mixing times of Markov chains, e.g., the rate of convergence of Markov chains to stationary measures. We focus on Glauber dynamics for the (classical) Ising model as well as random walks on random graphs.;We first provide a complete picture for the evolution of the mixing times and spectral gaps for the mean-field Ising model. In particular, we pin down the scaling window, and prove a cutoff phenomenon at high temperatures, as well as confirm the power law at criticality. We then move to the critical Ising model at Bethe lattice (regular trees), where the criticality corresponds to the reconstruction threshold. We establish that the mixing time and the spectral gap are polynomial in the surface area, which is the height of the tree in this special case. Afterwards, we show that the mixing time of Glauber dynamics for the (ferromagnetic) Ising model on an arbitrary n-vertex graph at any temperature has a lower bound of n log n/4, confirming a folklore theorem in the special case of Ising model.;In the second part, we study the random walk on the largest component of the near-supcritical Erdos-Renyi graph. Using a complete characterization of the structure for the near-supercritical random graph, as well as various techniques to bound the mixing times in terms of spectral profile, we obtain the correct order for the mixing time in this regime, which demonstrates a smooth interpolation between the critical and the supercritical regime.