Construction of an irreducible Markov chain in the Ising model

Construction of an Irreducible Markov Chain in the Ising model is a mathematical method to prove results.

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

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 $z\in Z^{N_{1}\times \cdots \times N_{d}}$ can be uniquely decomposed as $z=z^{+}-z^{-}$, where $z^{+}$ and $z^{-}$ are non-negative vectors. A Markov basis ${\widetilde {Z}}\subset Z^{N_{1}\times \cdots \times N_{d}}$ satisfies the following conditions:

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

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

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

and

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

for l = 1,...,k.

The element of ${\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 and (2) any generating set for the ideal $I:=\ker({\psi }*{\phi })$, is a Markov basis for the Ising model.

Construction of an Irreducible Markov Chain

To obtain uniform samples from $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 $z\in Z^{N_{1}\times \cdots \times N_{d}}$ of the form $z=e_{i}-e_{j}$, where $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 $y',y\in S(a,b)$ are $S(a,b)$-connected by Z if there exists a path between y and y′ consisting of simple swaps $z\in Z$.

The algorithm proceeds as follows:

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

with

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

for $l=1\ldots k$

The algorithm can now be described as:

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

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

(iii) Accept $y'$ if $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 overcomed by using the Metropolis-Hastings algorithm in the smallest expanded sample space $S^{\star }(a,b)$.

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 $S(a,b)$ for the 1-dimension Ising model is unique (up to location of its connected components) and consists of ${\frac {b}{2}}-1$ singletons and one connected component of size $a-{\frac {b}{2}}+1$.

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

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

and

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

for $l=1\ldots k$

Since $S^{\star }(a,b)$ is the smallest expanded sample space which contains $S(a,b)$, any two configurations in $S(a,b)$ can be connected by simple swaps Z without leaving $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.

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