为什么说 Metropolis 算法在临界点效率会很低呢，是否能稍微对比介绍一下聚类法和蠕虫算法？ 第1页

当年搜到这个题，结果到现在了都还没人答...那我就还来挖坟好了。简单的聊一聊然后引出大佬！

（忙完这阵子有空查查各种算法的 到底是几）

• 首先是临界慢化的事情：

在我们进行马尔科夫蒙特卡洛的过程中，我们认为在足够多次的跳转之后，得到的某样本是满足我们想要的分布的，比如，第10000个样本我们认为是从某概率分布中产生的，但对于第10001个样本，单独看其也是满足给定分布的，但显然这两个样本之间有着很强的关联，所以我们在实际蒙卡的过程中，在热化之后，需要间隔一定的步数采样，比如我们选取第10000个样本，第10100个样本，第10200个样本...为了使得样本之间尽量统计独立。

而间隔多少步合适，我们有自关联时间来表征：

， 其中 为第 步某观测量的值，指数衰减，其中 即为我们所说的自关联时间，我们一般要间隔超过自关联时间在进行下一次采样。

在相变点附近，系统具有长程关联，一般的更新方法效率低下，自关联时间很长，我们把这种现象叫做临界慢化。

显然，Metropolis是local的更新，自关联时间自然很长，每翻转格子一遍记做一次，我们的自关联时间 ，if没记错，对于二维伊辛模型， （反正是2点多啦）。然后Cluster更新的方法，诸如Swendsen–Wang算法 Wolff算法更好一些。

• 关于蠕虫算法：

最近感兴趣大概简单了解了一下，尝试对于Ising模型中进行蠕虫算法进行说明

首先我们是在Closed-path (CP) configurations下进行的，即某一种闭合路径对应某个构型。

我们设整个模型的格点数为 ，边的条数为

一般我们的方法是对配分函数的exp进行泰勒展开然后再相乘起来，不过对于Ising模型我们有一个强大的技巧：

，其中符号不言自明，在 时等式成立。

即对于伊辛模型的配分函数，我们能进行如下操作：

，其中

代入等式：

对于这个连乘，其各项必为 的形式且

我们把连乘时选到1认为未连接该边，选到 认为连接了边ij，则权重每项对应着一个和bond有关的构型。

我们知道因为求和 的缘故， 只有当为偶数时该项不为0，即对应着各顶点都连接了偶数条边的情况，即闭合路径。

则我们讲配分函数写为了： ，其中 为子图的边数。

当我们想测量诸如 时，我们有 :

即不同构型的权重正比于 ，其中 为该子图的边数。

则我们从Worm的头或尾开始随机游走，如选择从x点开始，向紧邻的点尝试走一步，如该条边以及在子图中了就删除该边，如该条边不在子图中，则以 的概率接受。这是我们早已熟悉的蒙卡的基本套路，跳转接收概率与权重之比有关： 其中 正比于权重， 为提议分布， 为接受概率。

Worm算法虽然是local的更新，但是在某些情况下，大家算出来其不怎么受临界慢化的影响，在相变点附近媲美最好的Cluster更新。

其他还有比如泰勒展开展开到 来在和bond有关的构型上搞蒙卡，庶几近之，只是没有Ising的那个技巧罢了。

暂时就简单介绍这么多，这两天换换脑子看了几眼Worm，随口跟导师大人聊了几句，导师说：“你要是对这个感兴趣，我可以把你送到合肥跟着邓老师待一段时间”，吓得我赶紧说不感兴趣不感兴趣。还是在所里跟陆老师等人踢球的日子美啊！！！

还是SSE大法好！！！（老板啊你手里的枪能不能放下了）

ps：为什么不去看看邓友金老师的Paper和note呢？http://staff.ustc.edu.cn/~yjdeng/lecturenotes/worms.pdf

疯狂翻页图就动起来了！！！性感Worm，在线蠕动！！！

以及我觉得问题里贴的这个http://mcwa.csi.cuny.edu/umass/izing/Ising_text.pdf可以说是已经非常清楚了...可以完全不需要看此回答此回答就是为了把这坟挖活罢了。