Construction of an irreducible Markov chain in the Ising model explained

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

	N_{1 x … x}N_d
Z

can be uniquely decomposed as

z=z^+-z^-

, where

z⁺

and

z^-

are non-negative vectors. A Markov basis

\widetilde{Z}\subsetZ

	N_{1 x … x}N_d

satisfies the following conditions:

(i) For all

z\in\widetilde{Z}

, there must be

	-)
T
	1(z

and

	-)
T
	2(z

(ii) For any

a,b\inZ_>0

and any

x,y\inS(a,b)

, there always exist

z_1,\ldots,z_k\in\widetilde{Z}

satisfy:

	k
y=x+\sum
	i=1

z_i

and

	l
x+\sum
	i=1

z_i\inS(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^[2] and (2) any generating set for the ideal

I:=\ker({\psi}*{\phi})

, is a Markov basis for the Ising model.^[3]

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

	N_{1 x … x}N_d
Z

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\inS(a,b)

are

S(a,b)

-connected by Z if there exists a path between y and y′ consisting of simple swaps

z\inZ

The algorithm proceeds as follows:

	k
y'=y+\sum
	i=1

z_i

with

	l
y+\sum
	i=1

z_i\inS(a,b)

for

l=1\ldotsk

The algorithm can now be described as:

(i) Start with the Markov chain in a configuration

y\inS(a,b)

(ii) Select

z\inZ

at random and let

y'=y+z

(iii) Accept

y'\inS(a,b)

; otherwise remain in y.

S^\star(a,b)

.^[4]

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

	b
	2

-1

singletons and one connected component of size

	b
	2

Lemma 2: For

a,b\inN

and

y\inS(a,b)

, let

y^\starS(a,b)

denote the unique max-singleton configuration. There exists a sequence

z_1,\ldots,z_k\inZ

such that:

y^\star

	k
=y+\sum
	i=1

z_i

and

	l
y+\sum
	i=1

z_i\inS(a,b)

for

l=1\ldotsk

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

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

Notes and References

Kannan . Ravi . Ravindran Kannan . Mahoney . Michael W. . Montenegro . Ravi . 2003 . Ibaraki . Toshihide . Toshihide Ibaraki . Katoh . Naoki . Ono . Hirotaka . Algorithms and Computation, 14th International Symposium, ISAAC 2003, Kyoto, Japan, December 15-17, 2003, Proceedings . Lecture Notes in Computer Science . Springer . 2906 . 663–675 . 10.1007/978-3-540-24587-2_68 . Rapid mixing of several Markov chains for a hard-core model.
Diaconis . Persi . Sturmfels . Bernd . February 1998 . Algebraic algorithms for sampling from conditional distributions . The Annals of Statistics . en . 26 . 1 . 363–397 . 10.1.1.28.6847 . 10.1214/aos/1030563990 . 0090-5364 . 2023-11-16.
Robert . Christian P. . Casella . George . 2004 . Monte Carlo Statistical Methods . Springer Texts in Statistics . 10.1007/978-1-4757-4145-2 . 1431-875X.
Book: Levin, David . Markov Chains and Mixing Times . Peres . Yuval . Wilmer . Elizabeth . 2008-12-09 . American Mathematical Society . 978-0-8218-4739-8 . Providence, Rhode Island.
PESKUN . P. H. . 1973 . Optimum Monte-Carlo sampling using Markov chains . Biometrika . 60 . 3 . 607–612 . 10.1093/biomet/60.3.607 . 0006-3444.