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

This article has multiple issues. Please help improve it or discuss these issues on the talk page. (Learn how and when to remove these template messages) This article provides insufficient context for those unfamiliar with the subject. (June 2015) This article's tone or style may not reflect the encyclopedic tone used on Wikipedia. (June 2015) This article possibly contains original research. (June 2015)

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.^[1]

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

(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. 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,^[2] shows that a Markov basis can be defined algebraically as an Ising model. According to the paper, any generating set for the ideal ${\displaystyle I:=\ker({\psi }*{\phi })}$ is a Markov basis for the Ising model.

Without modifying the algorithm mentioned in the paper, it is impossible to get uniform samples from ${\displaystyle S(a,b)}$, otherwise leading to inaccurate p-values.^[3]

A simple swap is defined as ${\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 of ${\displaystyle 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 ${\displaystyle y',y\in S(a,b)}$ are ${\displaystyle S(a,b)}$-connected by Z, if there is a path between ${\displaystyle y}$ and ${\displaystyle y'}$ in ${\displaystyle S(a,b)}$ consisting of simple swaps ${\displaystyle z\in Z}$, which means there exists ${\displaystyle z_{1},\ldots ,z_{k}\in Z}$ such that:

${\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}$ uniformly 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, we can overcome this problem by using the Metropolis-Hastings algorithm in the smallest expanded sample space ${\displaystyle S^{\star }(a,b)}$.

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 components 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.

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