Mixing time for the Ising model and random walks
- Author(s): Ding, Jian
- Advisor(s): Peres, Yuval
- Mossel, Elchanan
- et al.
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