Construction of an irreducible Markov chain in the Ising model

Construction of an irreducible Markov Chain is a mathematical method used to prove results related the changing of magnetic materials in the Ising model, enabling the study of phase transitions and critical phenomena.

The Ising model, a mathematical model in statistical mechanics, is utilized to study magnetic phase transitions and is a fundamental model of interacting systems.^[1] Constructing an irreducible Markov chain within a finite Ising model is essential for overcoming computational challenges encountered when achieving exact goodness-of-fit tests with Markov chain Monte Carlo (MCMC) methods.

Markov bases

In the context of the Ising model, a Markov basis is a set of integer vectors that enables the construction of an irreducible Markov chain. Every integer vector ${\displaystyle z\in Z^{N_{1}\times \cdots \times N_{d}}}$ can be uniquely decomposed as ${\displaystyle z=z^{+}-z^{-}}$, where ${\displaystyle z^{+}}$ and ${\displaystyle z^{-}}$ are non-negative vectors. A Markov basis ${\displaystyle {\widetilde {Z}}\subset Z^{N_{1}\times \cdots \times N_{d}}}$ satisfies the following conditions:

(i) For all ${\displaystyle z\in {\widetilde {Z}}}$, there must be ${\displaystyle T_{1}(z^{+})=T_{1}(z^{-})}$ and ${\displaystyle T_{2}(z^{+})=T_{2}(z^{-})}$.

(ii) For any ${\displaystyle a,b\in Z_{>0}}$ and any ${\displaystyle x,y\in S(a,b)}$, there always exist ${\displaystyle z_{1},\ldots ,z_{k}\in {\widetilde {Z}}}$ satisfy:

${\displaystyle y=x+\sum _{i=1}^{k}z_{i}}$

and

${\displaystyle x+\sum _{i=1}^{l}z_{i}\in S(a,b)}$

for l = 1,...,k.

The element of ${\displaystyle {\widetilde {Z}}}$ is moved. An aperiodic, reversible, and irreducible Markov Chain can then be obtained using Metropolis–Hastings algorithm.

Persi Diaconis and Bernd Sturmfels showed that (1) a Markov basis can be defined algebraically as an Ising model^[2] and (2) any generating set for the ideal ${\displaystyle I:=\ker({\psi }*{\phi })}$, is a Markov basis for the Ising model.^[3]

Construction of an irreducible Markov Chain

To obtain uniform samples from ${\displaystyle S(a,b)}$ and avoid inaccurate p-values, it is necessary to construct an irreducible Markov chain without modifying the algorithm proposed by Diaconis and Sturmfels.

A simple swap ${\displaystyle z\in Z^{N_{1}\times \cdots \times N_{d}}}$ of the form ${\displaystyle z=e_{i}-e_{j}}$, where ${\displaystyle e_{i}}$ is the canonical basis vector, changes the states of two lattice points in y. The set Z denotes the collection of simple swaps. Two configurations ${\displaystyle y',y\in S(a,b)}$ are ${\displaystyle S(a,b)}$-connected by Z if there exists a path between y and y′ consisting of simple swaps ${\displaystyle z\in Z}$.

The algorithm proceeds as follows:

${\displaystyle y'=y+\sum _{i=1}^{k}z_{i}}$

with

${\displaystyle y+\sum _{i=1}^{l}z_{i}\in S(a,b)}$

for ${\displaystyle l=1\ldots k}$

The algorithm can now be described as:

(i) Start with the Markov chain in a configuration ${\displaystyle y\in S(a,b)}$

(ii) Select ${\displaystyle z\in Z}$ at random and let ${\displaystyle y'=y+z}$.

(iii) Accept ${\displaystyle y'}$ if ${\displaystyle y'\in S(a,b)}$; otherwise remain in y.

Although the resulting Markov Chain possibly cannot leave the initial state, the problem does not arise for a 1-dimensional Ising model. In higher dimensions, this problem can be overcome by using the Metropolis-Hastings algorithm in the smallest expanded sample space ${\displaystyle S^{\star }(a,b)}$.^[4]

Irreducibility in the 1-Dimensional Ising Model

The proof of irreducibility in the 1-dimensional Ising model requires two lemmas.

Lemma 1: The max-singleton configuration of ${\displaystyle S(a,b)}$ for the 1-dimension Ising model is unique (up to location of its connected components) and consists of ${\displaystyle {\frac {b}{2}}-1}$ singletons and one connected component of size ${\displaystyle a-{\frac {b}{2}}+1}$.

Lemma 2: For ${\displaystyle a,b\in N}$ and ${\displaystyle y\in S(a,b)}$, let ${\displaystyle y^{\star }S(a,b)}$ denote the unique max-singleton configuration. There exists a sequence ${\displaystyle z_{1},\ldots ,z_{k}\in Z}$ such that:

${\displaystyle y^{\star }=y+\sum _{i=1}^{k}z_{i}}$

and

${\displaystyle y+\sum _{i=1}^{l}z_{i}\in S(a,b)}$

for ${\displaystyle l=1\ldots k}$

Since ${\displaystyle S^{\star }(a,b)}$ is the smallest expanded sample space which contains ${\displaystyle S(a,b)}$, any two configurations in ${\displaystyle S(a,b)}$ can be connected by simple swaps Z without leaving ${\displaystyle S^{\star }(a,b)}$. This is proved by Lemma 2, so one can achieve the irreducibility of a Markov chain based on simple swaps for the 1-dimension Ising model.^[5]

It is also possible to get the same conclusion for a dimension 2 or higher Ising model using the same steps outlined above.