3.3.1. 基本模型与算法介绍

3.3.1.1. Ising 模型 与 Potts 模型

Ising 模型，是物理学家研究磁性材料的模型，在统计物理中已经被广泛的研究过了。一个相近的模型是 Potts 模型 。与Ising模型类似，Potts 模型也是定义在晶格空间 \(\mathcal{L}\) 上的 \(x=(x_l,x\in \mathcal{L})\) 。

\[\mathcal{L}=\{ l=(l_1,l_2)\ for\ l_1,l_2 = 1,\dots,N\}.\]

与Ising模型不同，在Potts 模型里面每一个 \(x_l\) 可以取 \(q:{1,\dots,q}\) 。能量势可以取为：

\[H(x)=-J\sum_{i\sim j}\delta_{x_ix_j}-\sum_{j}h_j(x_j)\]

这里 \(i\sim j\) 表示i和j在晶格空间里面是相邻的。于是我们关心的分布就是Bolzmann分布：

\[\pi(x) \propto exp\{-\beta H(x)\}\]

\(\beta=(kT)^{-1}\) ， \(k\) 是Bolzmann常数，T是绝对温度。当 \(q=2\) 时，Potts模型就是Ising模型：

\[H(x)=-\frac{1}{2}J\sum_{i\sim j}2(\delta_{x_ix_j}-\frac{1}{2})-\sum_{i\sim j}\frac{1}{2}J-\sum_{j}h_j(x_j)\]

为了简单起见，我们假设 \(h_j\equiv 0\) 。

关于这个模型的一个重要的问题是相变现象：当温度高的时候，可以观察到所有的spin几乎是独立变化的；而当温度低到一个特定的温度 \(c_0\) 以后，所有的spin就趋于保持一致。

标准的 Metropolis算法正好方便的应用于模拟这个模型：第一步，随机选一个spin将他的取值 \(x_l\) 取为 \(-x_l\) ； 第二步，计算 Metropolis 比例来决定是否接受这个变化。但是当温度接近或者低于 \(c_0\) 的时候，这个算法变的非常的慢。

3.3.1.2. 算法介绍

3.3.1.2.1. The Swendsen-Wang Algorithm as Data Augmentation

概念上，我们可以将 Swendsen-wang 算法视为一种“数据增强”（data augmentation scheme）。我们用一个连接变量 \(u=(u_{l\sim l'})\) 来增强数据。每一个 \(u_{l \sim l'}\) 在晶格的边界上，取值范围为： \([0,e^{2 \beta J}]\) 。

\[\begin{split}\pi(x)& \propto exp\{\beta J \sum_{l\sim l'}x_l x_{l'}\} \\ &\propto \prod_{l\sim l'}exp\{\beta J(1+ \sum_{l\sim l'}x_l x_{l'})\} \\\end{split}\]

注意到 \(1+x_l x_{l'}\) 等于 0 或者2。所以，如果我们引入辅助变量 \(u\) 使得：

\[\pi(x,u) \propto \prod_{l \sim l'} I[0 \leq u_{l,l'} \leq exp{\beta J(1+x_lx_{l'})}],\]

于是 x 的边界分布就是我们想要的分布。 显然，在这个联合分布中，条件分布 \([u|x]\) 是各个基于两个相邻的spin的平均分布的乘积。反过来，给定u，x的条件分布也容易得到：如果 \(u_{l,l'}>1\) ，则 \(x_l=x_{l'}\) ；否则对 \(x_l\) 没有限制。 于是，u 只有在 \(I[u_{l,l'}>1\) 时，对 x 起作用。基于u的作用，我们将这些晶格根据相互直接有没有连接来分成组（cluster）。然后，所有属于同一组的 \(x_l\) 必须保持相同的值。在这样的分组的前提下，没一种情况出现的概率都是相同的。

所以，我们还可以做另一种数据增强，只用一个 连接变量 \(b =(b_{l\sim l'}\) ,来表示 \(u(l,l')>1\) 是否成立。也就是说，我们定义：

\[b_{l,l'}= I[u_{l,l'}>1]\]

于是，相应的增强模型是：

\[\pi(x,b) \propto \prod_{x_l=x_{l'}}\{1+b_{l,l'}(e^{2 \beta J} - 1)\},\]

且 \(b_{l,l'}\) 如果 \(x_l\neq x_{l'}\) 。 spin的分组(clustering)可以通过将连接为1的邻居相连。分组之间的spin方向相互独立。

Swendsen-Wang 算法:

  • 对于一个给定的spin情况，以概率 \(1-e^{-2\beta J}\) 建立每一个相等晶格之间的边界的连接变量 \(\langle l,l' \rangle\) 取值为1 ，否则取值0。

  • 在连接变量 b 前提下，通过 \(p(x|b)\) 更新 spin变量x ,即在所有可能情况下的平均分布。也就是说，每一个组以概率 0.5 翻转。

3.3.1.2.2. The Modification by Wolff

Wolff的修正使得算法的效率得到了很大的改善：

Wolff 算法：

  • 对于给定的一个情况x，随机选取一个晶格 \(x_l\) ，然后从一个连接集 \(C\) 递归的生长：

  • 检查 \(C^{old}\) 所有未检查的邻居；并且按照 SW算法中的规则建立连接。

  • 将新连接到 \(C^{old}\) 上的单元添加到 \(C^{old}\) 中生成 \(C^{new}\)

  • 停止上诉递归过程直到没有未检查的邻居可以添加。将最后的集合称为 \(C\)

  • 将 集合 C 中的所有元素翻转，（不带随机性）。

3.3.1.2.3. Further Generalization

Niedermayer 提出允许连接取值不同的邻居。设 \(p_a\) 为连接相等邻居的概率， \(p_b\) 为连接相反邻居的概率。生长完一个组 \(C\) (Cluster)之后，反转整个 \(C\) 。 选取适当的 \(p_a,p_b\) 使得：

\[\frac{1-p_a}{1-p_b}=e^{2\beta J}\]