Coupling from the past 算法与 Markov 链的随机取样

本文是完美取样系列三部曲的最后一部,目的是介绍 Markov 链上的 coupling from the past 算法 (以下简称 CFTP )。之前的两部曲分别是多米诺洗牌算法和 Wilson 均匀生成树算法。

本文的代码在 github 上。

这三个算法的目的都是从某些很大很大的集合当中以给定的概率分布随机取样,区别在于它们针对的集合不同。多米诺洗牌算法是在 Aztec 钻石图的所有密铺中取样;Wilson 算法是在一个图的所有生成树中取样;而 CFTP 算法则是在一个 Markov 链的状态空间中按照其平稳分布取样。

我们先考虑一个看起来很初等的问题:

问题 1:下图是一个边长分别为 \(a,b,c\) 的平行六边形,其中 \(a,b,c\) 都是正整数,内角均为 120 度:

请问:用边长为 1 的菱形密铺它,有多少种不同的方法?

递降平面分拆的 Andrews 猜想

前言

你可能经常听到这样一句话:“做数学要大胆假设,小心求证”。我们今天要介绍的故事主角平面分拆中的 Andrews 猜想就完美地符合这一点。两个看似风马牛不相及的计数对象,因为有着相同的计数序列,冥冥中被联系在了一起,启发三位数学家 Mill, Robins 和 Rumsey 解决了一个困难的组合学猜想。整个过程并无高深的内容,但是其中的“信仰一跃”和“灵魂一猜”构成了故事的高潮,而那些繁琐的计算过程不过是小心求证的注脚而已。

本文来自我几年前读 David Bressoud 的

Proofs and Confirmations: The Story of the Alternating Sign Matrix Conjecture

一书时的读书笔记,但是叙述与 Bressoud 的书不同:Bressoud 是把 DPP 的 Andrews 猜想和 CSPP 的 Macdonald 猜想统一用 \(q-\) 超几何级数一起解决的,因此理论较为复杂。由于 Macdonald 猜想的证明似乎无法避免使用超几何级数的理论,而本人水平不足,没有看懂这一部分,所以这里只介绍 DPP 的 Andrews 猜想,并仅使用初等的 \(q-\) 二项式定理作为工具,所以计算步骤会显得有些繁琐。

Wilson 均匀生成树算法

在距离本文初稿完成数年后,我终于实现了一个 Python 程序,可以制作演示 Wilson 算法的 gif 动图,见我的这个 github 项目。此外还用 Javascript + canvas 为本文写了一个动画演示,这也是我的第一个正式的 Javascript 程序 (其实就是把对应的 Python 程序修改下翻译了过来),你可以随时单击鼠标来重启动画。

Birkhoff 遍历定理

Birkhoff 遍历定理最初由 Birkhoff 本人在 1931 年发表,原文长达 50 页。随后在 1939 年 K.Yosida (吉田耕作) 和 S.Kakutani (角谷) 利用极大遍历定理给出了一个 10 页的简洁证明,不过他们关于极大遍历定理的证明还是啰嗦了点,后来 Garsia 给出了极大遍历定理的一个仅有寥寥数行的惊人证明,这也是当前大多数教材采用的途径 (比如 Durrett 的书),本文就来介绍这一证明。

称硬币问题、小白鼠找毒药问题与编码理论

本文要讨论的问题比较常见,但是好像很少有人从纠错码的角度给出解释。从纠错码的角度看问题的好处是可以很容易理解为什么要这样设计策略,而且能举一反三处理其它类似的问题。事实上我觉得这种趣味问题正是帮助初学者理解纠错码基本概念的绝好例子。

不过本文并不假定读者事先学过编码论,但是需要懂一点有限域的知识。

称硬币问题

问题:有 12 枚外表一模一样的硬币,其中一枚是假币,其余都是真币。假币的重量与真币不同,但是更重还是更轻不知道。给你一个没有砝码和刻度的天平,最少称几次才能确保找出假币?

有限群的不可约实表示和复表示

在数学中有许多“三分天下”的例子,比如说:

  1. 常曲率空间只有欧式、球面、双曲三种。
  2. 三类典型的偏微分方程:热方程 (抛物)、Laplace 方程 (椭圆)、波方程 (双曲)。
  3. 复平面上全纯等价下只有三种单连通区域: 单位圆 \(\mathbb{D}\)、复平面 \(\mathbb{C}\)、扩充复平面 \(\bar{\mathbb{C}}\)
  4. 不可约代数簇 (素理想) 在扩张下的三种行为:分解、惯性、分歧。
  5. 随机游动可以分为零常返、正常返、暂态。
  6. 三维空间中的正多面体 (Platonic solids) 只有三种可能的对称群:\(S_4\) (tetrahedron)、\(S_4\times\mathbb{Z}_2\) (cube, octahedron)、\(A_5\times\mathbb{Z}_2\) (dodecahedron, icosahedron)。
  7. 实数域上的有限维结合可除代数只有三种:实数域 \(\mathbb{R}\)、复数域 \(\mathbb{C}\)、四元数 \(\mathbb{H}\)

本文要介绍的是另外两个“三分天下”的例子,它们来自群表示论,即有限群不可约复表示在实数域上的实现与不可约实表示在复数域上的分解,这两个例子是紧密相关的。

相亲问题与倒向归纳法

问题:假设你是一位大龄男士,准备参加 100 场相亲 (别介意具体数字)。你打算依次与每个女士 \(i\) 约会,然后根据印象给她打一个分数 \(X_i\)\(X_i\) 的值介于 \([0,1]\) 之间。如果你对女士 \(i\) 很满意,那么就和她结婚,否则就放弃她,参加下一场相亲,当然拒绝了人家可就没有回头的机会了。如果你拒绝了前 99 位女士,那么不论第 100 次相亲结果如何你都只能和最后这位女士结婚。在相亲之前,你对这些女士的情况一无所知,所以姑且假定她们的分数 \(X_i\) 都是 \([0,1]\) 上均匀分布的独立的随机变量。问题是:应该采取怎样的相亲策略,才能娶到你最中意的女士?

三质点弹簧系统的简正模式

今天的问题是群表示论在物理中的一个小应用:

问题:平面上有三个质量均为 \(m\) 的质点 \(A,B,C\),它们位于一个正三角形的三个顶点处。质点之间两两由一根弹簧相连,三个弹簧都是一样的,但是弹簧质量忽略不计。

初始时所有质点都处于静止状态,弹簧之间没有张力。假设给这三个质点分别施加一个初始速度,使这三个质点在平面内作刚体运动,不考虑任何摩擦力和空气阻力。那么这个系统的简正模式 (normal mode) 是什么?

这里简正模式的含义是所有质点按照一个共同的频率和固定的相位关系相对于各自的平衡位置作简谐振动。

模式的等待时间与反直觉概率

著名概率学家 Feller 在他的名著《An introduction to probability and its applications》中提到了这样一个实验:

重复抛掷一枚均匀的硬币,用 H 代表正面向上,T 代表背面向上,一直到连续出现 6 次 H 为止。这里连续 6 个 组成的模式记作 HHHHHH,所需要抛掷硬币的次数叫做等待时间。等待时间是一个随机变量,最小值是 6,最大值可以是无限。Feller 问:等待时间的均值是多少?

这个问题可以用 Markov 链来解,但是非常繁琐。香港中文大学李硕彦教授在他的论文

A Martingale Approach to the Study of Occurrence of Sequence Patterns in Repeated Experiments.

中用离散鞅的知识给出了一个简洁而巧妙的解法,本文就来介绍他的方法。

洛奇绵羊问题

我们的问题源自中世纪威尔士人的故事集《Mabinogion》中的一段:

一个男孩来到了一个美丽的山谷,有一条小河在谷中流淌。他看到河一边的草地上有一群黑绵羊,另一边的草地上有一群白绵羊。羊群被施以一种魔法:每个时刻都恰有一只绵羊发出咩咩的叫声。如果发出叫声的是白绵羊,就会有一只黑绵羊趟过小河跑过来并且变成白绵羊;如果发出叫声的是黑绵羊,则会有一只白绵羊趟过小河跑过去并且变成黑绵羊。每个时刻发出叫声的绵羊是完全随机的,整个过程没有绵羊出生或者死亡,一直持续到所有绵羊都变成同一种颜色为止。

问题是这样的:

问题:如果男孩可以选择在初始时刻 \(0\),或者是每个魔法时刻 \(1,2,\ldots\) 结束后将任意数量的白绵羊赶出山谷,那么为了最终得到尽可能多的黑绵羊,他应该采取怎样的策略?

当前网速较慢或者你使用的浏览器不支持博客特定功能,请尝试刷新或换用Chrome、Firefox等现代浏览器