UC Berkeley

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 Erd\"os-R {e}nyi 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.