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. 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 $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 $\tilde{Z}\subset Z^{N_1\times \cdots \times N_d}$ satisfies the following conditions:

(i) For all $z\in \tilde{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,\dots ,z_k\in \tilde{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 $\tilde{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 *\varphi )$, 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^{\prime },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^{\prime }=y+\sum _{i=1}^k{z}_i$

with

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

for $l=1\dots 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^{\prime }=y+z$.

(iii) Accept $y^{\prime }$ if $y^{\prime }\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 $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,\dots ,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\dots 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.