Construction of an irreducible Markov chain in the Ising model

Markov bases

For every integer vector z ∈ Z N 1 × ⋯ × N d , we can uniquely write it as z = z + − z − , where z + and z − are nonnegative vectors. Then the Markov basis in Ising model can be degined as:

A Markov bases for the Ising model is a set Z ~ ⊂ Z N 1 × ⋯ × N d os integer vector such that:

(i) For all z ∈ Z ~ there must be T 1 ( z + ) = T 1 ( z − ) and T 2 ( z + ) = T 2 ( z − ) .

(ii) For any a , b ∈ Z > 0 and any x , y ∈ S ( a , b ) there always exist z 1 , … , z k ∈ Z ~ satisfy

and

for l = 1,...,k.

The element of Z ~ is move. Then using the Metropolis–Hastings algorithm, we can get an aperiodic, reversible and irreducible Markov Chain.

The paper published by P.DIACONIS AND B.STURMFELS in 1998 ‘Algebraic algorithms for sampling from conditional distributions’ shows that a Markov basis can be defined algebraically as in Ising model

Then by the paper published by P.DIACONIS AND B.STURMFELS in 1998, any generating set for the ideal I := ker ⁡ ( ψ ∗ ϕ ) is a Markov basis for the Ising model.

Construction of an irreducible Markov chain

We cannot get a uniform samples from S ( a , b ) and lead to inaccurate p-value. Thus in the following we will show how to modify the algorithm mentioned in the paper to get the irreducible Markov chain in Ising model.

A simple swap is defined as z ∈ Z N 1 × ⋯ × N d of the form z = e i − e j , where the e i is the canonical basis vector of z ∈ Z N 1 × ⋯ × N d Simple swaps changes the states of two lattice points in y.

Z denotes the set of sample swaps. Then two configurations y ′ , y ∈ 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 ∈ Z , which means there exist z 1 , … , z k ∈ Z such that

with

for l = 1,...,k

The algorithm can be describe as:

(i) Start with the Markov chain in a configuration y ∈ S ( a , b )

(ii) Select z ∈ Z uniformly at random and let y ′ = y + z .

(iii) Accept y ′ if y ′ ∈ S ( a , b ) ; otherwise remain in y.

Although the resulting Markov Chain is possible cannot leave initial states, the problem does not arise for the 1 dimensional Ising model which we will introduce in the following. In high dimension we can overcome this problem by using Metropolis-Hastings algorithm in the smallest expanded sample space S ⋆ ( a , b )

Irreducibility in the 1-dimensional Ising model

Before prove of the irreducibility in 1-dimensional Ising model, we present two lemma below:

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 components of size a − b/2 + 1.

Lemma 2:For a , b ∈ N and y ∈ S ( a , b ) , let y ⋆ S ( a , b ) denote the unique max-singleton configuration. There exists a sequence z 1 , … , z k ∈ Z such that:

and

for l = 1,...,k

Since S ⋆ ( a , b ) is the smallest expanded sample space, which contains S ( a , b ) . And any two configurations in S ( a , b ) can be connected by simple swaps Z without leaving S ⋆ ( a , b ) . This can be prove by the lemma we present above. So we an get the irreducibility of the Markov Chain based on simple swaps for the 1-dimension Ising model.

Conclusion

Even though we just show the irreducibility of the Markov chain based on simple swaps for the 1-dimension Ising model, we can get the same conclusion of 2-dimension or higher dimension Ising model.