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-\) 二项式定理作为工具,所以计算步骤会显得有些繁琐。

有限维复半单李代数的 Weyl 特征公式

本文源自我学习 Humphreys 的教材 1 第六章 "Representation theory" 时的读书笔记,目的是介绍有限维复半单李代数的 Weyl 特征公式。Humphreys 的书是李代数课程默认的必读经典,它看着很薄,不免给人一种“我可以一个月”搞定的错觉,但我初学的时候觉得这本书并不容易读,现在回头来看才深感作者叙述之精炼。由于本文的内容直接从 Humphreys 教材的第六章开始,所以需要读者对之前章节的内容有一些基本的了解,但本文采用的叙述并不完全与 Humphreys 一致。

Wilson 均匀生成树算法

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

Coxeter element: a computational approach

虽然本文起了个英文标题,但内容完全是中文的,原因是我没有想到合适的能概括内容的中文标题。

相信很多人都见过下面的图案:(参考维基百科的 Lie algebra 词条)

它展示的是李代数 \(E_8\) 的根系图,李代数 \(E_8\) 的根系由八维欧式空间 \(\mathbb{R}^8\) 中的 240 个向量组成,每个向量恰好有 56 个与其距离最近的邻居。将这 240 个向量投影到一个特殊的二维平面 (叫做 Coxeter 平面) 就会呈现一个旋转对称的图案,你可以看到上图中的图案中,240 个投影点分布在 8 个圆周上,每个圆周包含 30 个均匀分布的顶点,所以它在角度为 \(\frac{2\pi}{30}\) 的旋转下是不变的。\(h=30\) 叫做 \(E_8\) 的 Coxeter 数。

这个现象并不是 \(E_8\) 独有的,对任何有限 Coxeter 群都有类似的结论成立,比如下图显示的是将 5 维超立方体的 32 个顶点投影到其 Coxeter 平面后得到的图案:

可以看到有两个顶点被同时投影到了原点,其余 30 个顶点分布在 3 个圆周上,每个圆周包含 10 个均匀分布的顶点,所以其 Coxeter 数 \(h=10\)

所以这个特殊的投影平面是怎么来的?本文下面以 \(E_8\) 为例子,通过具体的计算来解释背后的数学。

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}\)

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

 | 

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