Построение неприводимой цепи Маркова в модели Изинга

Построение неприводимой цепи Маркова в модели Изинга — математический метод доказательства результатов.

Модель Изинга — математическая модель статистической механики — используется для изучения магнитных фазовых переходов и является фундаментальной моделью взаимодействующих систем. Построение неприводимой цепи Маркова в модели Изинга имеет важное значение для преодоления вычислительных проблем, возникающих при использовании методов Монте-Карло (MCMC) цепи Маркова для достижения точных критериев согласия для конечных моделей Изинга.

Марковские базы

В контексте модели Изинга базис Маркова — это набор целочисленных векторов, который позволяет построить неприводимую цепь Маркова. Каждый целочисленный вектор $z\in Z^{N_{1}\times \cdots \times N_{d}}$ можно однозначно разложить как $z=z^{+}-z^{-}$, где $z^{+}$ и $z^{-}$ являются неотрицательными векторами . Марковский базис ${\widetilde {Z}}\subset Z^{N_{1}\times \cdots \times N_{d}}$ удовлетворяет следующим условиям:

(и) Для всех $z\in {\widetilde {Z}}$, должно быть $T_{1}(z^{+})=T_{1}(z^{-})$ и $T_{2}(z^{+})=T_{2}(z^{-})$.

(ii) Для любого $a,b\in Z_{>0}$ и любой $x,y\in S(a,b)$, всегда существуют $z_{1},\ldots ,z_{k}\in {\widetilde {Z}}$ удовлетворить:

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

и

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

для l = 1,..., k .

Элемент ${\widetilde {Z}}$ перемещается. можно получить апериодическую, обратимую и неприводимую цепь Маркова Затем с помощью алгоритма Метрополиса – Гастингса .

Перси Диаконис и Бернд Штурмфельс показали, что (1) марковский базис можно определить алгебраически как модель Изинга. и (2) любой порождающий набор для идеала $I:=\ker({\psi }*{\phi })$, является марковским базисом модели Изинга.

Построение неприводимой цепи Маркова.

Для получения однородных образцов из $S(a,b)$ и избежать неточных значений p , необходимо построить неприводимую цепь Маркова, не изменяя алгоритм, предложенный Диаконисом и Штурмфельсом.

Простой обмен $z\in Z^{N_{1}\times \cdots \times N_{d}}$ формы $z=e_{i}-e_{j}$, где $e_{i}$ — канонический базисный вектор, изменяет состояния двух точек решетки в y . Множество Z обозначает набор простых перестановок. Две конфигурации $y',y\in S(a,b)$ являются $S(a,b)$-связан через Z , если существует путь между y и y′, состоящий из простых перестановок $z\in Z$.

Алгоритм действует следующим образом:

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

с

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

для $l=1\ldots k$

Алгоритм теперь можно описать так:

(i) Начните с цепи Маркова в конфигурации $y\in S(a,b)$

(ii) Выберите $z\in Z$ наугад пусть и $y'=y+z$.

(iii) Принять $y'$ если $y'\in S(a,b)$; в противном случае оставайтесь в y .

Хотя полученная цепь Маркова, возможно, не сможет выйти из исходного состояния, для одномерной модели Изинга проблема не возникает. В более высоких измерениях эту проблему можно решить, используя алгоритм Метрополиса-Гастингса в наименьшем расширенном пространстве выборки. $S^{\star }(a,b)$.

Неприводимость в одномерной модели Изинга

Доказательство неприводимости в одномерной модели Изинга требует двух лемм .

Лемма 1. Максимально-одноэлементная конфигурация $S(a,b)$ для одномерной модели Изинга единственна (с точностью до расположения ее связных компонент) и состоит из ${\frac {b}{2}}-1$ синглтоны и один связный компонент размера $a-{\frac {b}{2}}+1$.

Лемма 2: Для $a,b\in N$ и $y\in S(a,b)$, позволять $y^{\star }S(a,b)$ обозначают уникальную конфигурацию max-singleton. Существует последовательность $z_{1},\ldots ,z_{k}\in Z$ такой, что:

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

и

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

для $l=1\ldots k$

С $S^{\star }(a,b)$ это наименьшее расширенное пространство выборки, содержащее $S(a,b)$, любые две конфигурации в $S(a,b)$ можно соединить простыми свопами Z не выходя $S^{\star }(a,b)$. Это доказывается леммой 2, поэтому можно добиться неприводимости цепи Маркова, основанной на простых заменах одномерной модели Изинга.

Также возможно получить тот же вывод для модели Изинга размерности 2 или выше, используя те же шаги, которые описаны выше.