Construction of an irreducible Markov chain in the Ising model

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

(i) For all $z\backslash in\; \backslash widetilde\{Z\}$, there must be $T\_1(z^+)=T\_1(z^-)$ and $T\_2(z^+)=T\_2(z^-)$.

(ii) For any $a,b\backslash in\; Z\_\{>0\}$ and any $x,y\backslash in\; S(a,b)$, there always exist $z\_1,\backslash ldots,z\_k\; \backslash in\; \backslash widetilde\{Z\}$ satisfy:

: $y=x+\backslash sum\_\{i=1\}^k\; z\_i$

and

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

for l = 1,...,k.

The element of $\backslash 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{{Cite journal |last1=Diaconis |first1=Persi |last2=Sturmfels |first2=Bernd |date=February 1998 |title=Algebraic algorithms for sampling from conditional distributions |url=http://projecteuclid.org/euclid.aos/1030563990 |journal=The Annals of Statistics |language=en |volume=26 |issue=1 |pages=363–397 |citeseerx=10.1.1.28.6847 |doi=10.1214/aos/1030563990 |issn=0090-5364 |access-date=2023-11-16}} and (2) any generating set for the ideal $I:=\backslash ker(\{\backslash psi\}*\{\backslash phi\})$, is a Markov basis for the Ising model.{{Cite journal |last=Robert |first=Christian P. |last2=Casella |first2=George |date=2004 |title=Monte Carlo Statistical Methods |url=http://dx.doi.org/10.1007/978-1-4757-4145-2 |journal=Springer Texts in Statistics |doi=10.1007/978-1-4757-4145-2 |issn=1431-875X}}

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\backslash in\; Z^\{N\_1\backslash times\backslash cdots\backslash 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\text{'},y\backslash 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\backslash in\; Z$.

The algorithm proceeds as follows:

: $y\text{'}=y+\backslash sum\_\{i=1\}^k\; z\_i$

with

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

for $l\; =\; 1\backslash ldots\; k$

The algorithm can now be described as:

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

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

(iii) Accept $y\text{'}$ if $y\text{'}\backslash 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^\{\backslash star\}(a,b)$.{{Cite book |last=Levin |first=David |url=http://dx.doi.org/10.1090/mbk/058 |title=Markov Chains and Mixing Times |last2=Peres |first2=Yuval |last3=Wilmer |first3=Elizabeth |date=2008-12-09 |publisher=American Mathematical Society |isbn=978-0-8218-4739-8 |location=Providence, Rhode Island}}

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 $\backslash frac\{b\}\{2\}\; -\; 1$ singletons and one connected component of size $a\; -\; \backslash frac\{b\}\{2\}\; +\; 1$.

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

: $y^\{\backslash star\}=y+\backslash sum\_\{i=1\}^k\; z\_i$

and

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

for $l\; =\; 1\backslash ldots\; k$

Since $S^\{\backslash 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^\{\backslash 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.{{Cite journal |last=PESKUN |first=P. H. |date=1973 |title=Optimum Monte-Carlo sampling using Markov chains |url=http://dx.doi.org/10.1093/biomet/60.3.607 |journal=Biometrika |volume=60 |issue=3 |pages=607–612 |doi=10.1093/biomet/60.3.607 |issn=0006-3444}}

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

{{Reflist}}

Category:Lattice models

Category:Markov chain Monte Carlo