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.

In applied mathematics, the construction of an irreducible Markov Chain in the Ising model is the first step in overcoming a computational obstruction encountered when a Markov chain Monte Carlo method is used to get an exact goodness-of-fit test for the finite Ising model.

The Ising model is used to study magnetic phase transitions and is one of the models of interacting systems.

Markov bases

Every integer vector $z\in Z^{N_{1}\times \cdots \times N_{d}}$, can be uniquely written as $z=z^{+}-z^{-}$, where $z^{+}$ and $z^{-}$ are nonnegative vectors. A Markov basis for the Ising model is a set ${\widetilde {Z}}\subset Z^{N_{1}\times \cdots \times N_{d}}$ of integer vectors such that:

(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. Then, by using the Metropolis–Hastings algorithm, we can get an aperiodic, reversible, and irreducible Markov Chain.

The paper "Algebraic algorithms for sampling from conditional distributions", published by Persi Diaconis and Bernd Sturmfels in 1998, shows that a Markov basis can be defined algebraically as an Ising model. According to the paper, any generating set for the ideal $I:=\ker({\psi }*{\phi })$ is a Markov basis for the Ising model.

Construction of an irreducible Markov Chain

Without modifying the algorithm mentioned in the paper, it is impossible to get uniform samples from $S(a,b)$, otherwise leading to inaccurate p-values.

A simple swap is defined as $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 of $z\in Z^{N_{1}\times \cdots \times N_{d}}$. Simple swaps change the states of two lattice points in y.

Z denotes the set of sample swaps. Then two configurations $y',y\in S(a,b)$ are $S(a,b)$-connected by Z, if there is a path between $y$ and $y'$ in $S(a,b)$ consisting of simple swaps $z\in Z$, which means there exists $z_{1},\ldots ,z_{k}\in Z$ such that

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

with

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

for l=1,...,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$ uniformly 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, we can overcome this problem 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 components 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,...,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 we an get the irreducibility of the 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 via the above steps.