Overview
This research examines the convergence properties, specifically the mixing time of local Markov chains, for ferromagnetic Ising and spin glass models. The study identifies conditions under which these models exhibit slow mixing, requiring computation times that scale exponentially with the system size.
Research Context
The ferromagnetic Ising model, when configured on an $n \times n$ square lattice region $\Lambda$ with mixed boundary conditions, can undergo a phase transition as temperature varies. Specifically, if the spins on the top and bottom sides of the square are fixed to $+$ and the left and right sides to $-$, a phenomenon of slow mixing of local Markov chains has been observed. A standard Peierls argument based on energy indicates that below a critical temperature $t_c$, any local Markov chain $\mathcal{M}$ requires time exponential in $n$ to mix.
Spin glasses extend the Ising model by allowing for specification of nearest-neighbor interaction strengths on the lattice, including both ferromagnetic and antiferromagnetic interactions. A face of the lattice is considered frustrated if it is bounded by an odd number of edges with ferromagnetic interactions, implying that local competing objectives cannot be simultaneously satisfied.
Approach
The study considers spin glasses characterized by exactly four well-separated frustrated faces. These frustrated faces are positioned symmetrically around the center of the lattice region, exhibiting $90$ degree rotational symmetry. The researchers investigated the mixing time for local Markov chains across all spin glasses within this defined class.
The methodology extends to the ferromagnetic Ising model with mixed boundary conditions, by framing its behavior in terms of spin glasses with frustrated faces located on the boundary. The research addresses limitations of the standard Peierls argument, which typically breaks down when frustrated faces are in the interior of $\Lambda$ or yields weaker results for boundary frustrated faces not near corners.
The argument for slow mixing relies on demonstrating an exponentially small cut, indicated by the free energy. This involves carefully exploiting both entropy and energy to establish a small bottleneck within the state space, which is then used to demonstrate slow mixing.
Findings
- For the ferromagnetic Ising model on an $n \times n$ square lattice region $\Lambda$ with mixed boundary conditions (top/bottom spins fixed to $+$, left/right to $-$), local Markov chains $\mathcal{M}$ require time exponential in $n$ to mix below a critical temperature $t_c$. This is supported by a standard Peierls argument based on energy.
- For spin glasses with exactly four well-separated frustrated faces, symmetric around the lattice center under $90$ degree rotations, local Markov chains require exponential time for all spin glasses in this class.
- The argument for slow mixing in spin glasses with frustrated faces extends to the ferromagnetic Ising model with mixed boundary conditions, which behaves similarly to spin glasses having frustrated faces on the boundary.
- A universal temperature $T$ exists, below which local Markov chains $\mathcal{M}$ will be slow for all spin glasses with four well-separated frustrated faces.
- The mechanism for slow mixing involves an exponentially small cut, identified by the free energy, which arises from a bottleneck in the state space determined by the interplay of entropy and energy.