Misplaced Pages

This article has multiple issues. Please help improve it or discuss these issues on the talk page. (Learn how and when to remove these messages) This article provides insufficient context for those unfamiliar with the subject. Please help improve the article by providing more context for the reader. (June 2015) (Learn how and when to remove this message) This article's tone or style may not reflect the encyclopedic tone used on Misplaced Pages. See Misplaced Pages's guide to writing better articles for suggestions. (June 2015) (Learn how and when to remove this message) This article possibly contains original research. Please improve it by verifying the claims made and adding inline citations. Statements consisting only of original research should be removed. (June 2015) (Learn how and when to remove this message) (Learn how and when to remove this message)

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

(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. 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 ${\displaystyle I:=\ker({\psi }*{\phi })}$, is a Markov basis for the Ising model.

Construction of an irreducible Markov Chain

To obtain uniform samples from ${\displaystyle 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 ${\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, changes the states of two lattice points in y. The set Z denotes the collection of simple swaps. Two configurations ${\displaystyle y',y\in S(a,b)}$ are ${\displaystyle S(a,b)}$-connected by Z if there exists a path between y and y′ consisting of simple swaps ${\displaystyle z\in Z}$.

The algorithm proceeds as follows:

${\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}$ 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, this problem can be overcome by using the Metropolis-Hastings algorithm in the smallest expanded sample space ${\displaystyle 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 ${\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 component 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.

References

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

• Lattice models
• Markov chain Monte Carlo