A to Z guide of essential oils • Zia Zensations

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

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 the Ising model is essential for overcoming computational challenges encountered when employing Markov chain Monte Carlo (MCMC) methods to achieve exact goodness-of-fit tests for finite Ising models.

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

(i) For all $z\in {\widetilde {Z}}$ , there must be $T_{1}(z^{+})=T_{1}(z^{-})$ and $T_{2}(z^{+})=T_{2}(z^{-})$ .

(ii) For any $a,b\in Z_{>0}$ and any $x,y\in S(a,b)$ , there always exist $z_{1},\ldots ,z_{k}\in {\widetilde {Z}}$ satisfy:

y=x+\sum _{i=1}^{k}z_{i}

and

x+\sum _{i=1}^{l}z_{i}\in S(a,b)

for l=1,...,k.

The element of ${\widetilde {Z}}$ is moved. Then, by using the Metropolis–Hastings algorithm, we can get an aperiodic, reversible and irreducible Markov Chain.

Persi Diaconis and Bernd Sturmfels showed that, a Markov basis can be defined algebraically as an Ising model^[2] and, 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 Z^{N_{1}\times \cdots \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',y\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\in Z$ .

The algorithm proceeds as follows:

y'=y+\sum _{i=1}^{k}z_{i}

with

y+\sum _{i=1}^{l}z_{i}\in S(a,b)

for $l=1\ldots k$

The algorithm can now be described as:

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

(ii) Select $z\in Z$ at random and let $y'=y+z$ .

(iii) Accept $y'$ if $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 overcomed by using the Metropolis-Hastings algorithm in the smallest expanded sample space $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 ${\frac {b}{2}}-1$ singletons and one connected components of size $a-{\frac {b}{2}}+1$ .

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

y^{\star }=y+\sum _{i=1}^{k}z_{i}

and

y+\sum _{i=1}^{l}z_{i}\in S(a,b)

for $l=1\ldots k$

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.

References

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

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

[1]

[2]

[3]

[4]

[5]

Markov bases

Construction of an Irreducible Markov Chain

Irreducibility in the 1-Dimensional Ising Model

References

Useful Links

Hours & Info

Address

Contact

BBB Rating

Verify you are at least 21 years old to buy smokeables