问题： 给定一个有限、无向的连通图 \(G= ( V,E )\)，设 \(\mathcal{T}\) 是 \(G\) 的所有生成树组成的集合，怎样在 \(\mathcal{T}\) 中按照均匀分布进行采样？即设计一个算法，能够随机地给出 \(G\) 的一个生成树，并且 \(\mathcal{T}\) 中每个生成树被取到的概率是相等的。
常见的生成树算法如 DFS/BFS 算法、Prim 算法、Kruskal 算法等给出的生成树都不是完全随机的。例如，取 \(G\) 为 \(\mathbb{Z}^2\) 中 \(m\times n\) 的网格图，\(G\) 的任何生成树都是一个迷宫，把背景平面涂黑，把生成树的边涂白，就可以清楚地看到迷宫的结构。迷宫的任何两个房间 ( 即顶点 ) 可以通过生成树中唯一的路径相连，这样的迷宫叫做完美迷宫。
DFS 算法 ( 每次将新顶点的顺序打乱再入栈 ) 倾向于尽可能深地探索整个图，因此得到的迷宫往往包含长且蜿蜒的路径，死角 ( 即叶节点 ) 是很少的：
如果你对 Lie 代数有所了解的话，相信很大概率你会见过下面的图案： ( 参考维基百科的 Lie algebra 词条 )
它展示的是 Lie 代数 \(E_8\) 的根系图。\(E_8\) 的根系由 8 维欧式空间 \(\mathbb{R}^8\) 中的 240 个向量组成，将这 240 个向量投影到一个特殊的 2 维平面 ( 叫做 Coxeter 平面 ) 上就会呈现出一个具有旋转对称的图案。在上图中可以看到，240 个投影点分布在 8 个圆周上，每个圆周包含 30 个均匀分布的点，整个图案在角度为 \(\frac{2\pi}{30}\) 的旋转下是不变的。\(h=30\) 正是 \(E_8\) 的 Coxeter 数。
本文目的是介绍 Coxeter 元的一些基础知识，然后教大家怎样在 Python 中编写一个程序绘制上面的投影图案。我主要参考了 (Humphreys 1990) 和 (Casselman 2017)。虽然这里面涉及的数学并不复杂，但是真正动手编程实现的时候会有一些魔鬼藏在细节中，而这些细节是仅凭念书很难发现的。
本文的代码在 Github 上 。David Madore 也有一个很棒的 交互式网页 可以绘制 \(E_8\) 的多种不同风格的图案。
我念研究生时的高等概率论课用的是 Durrett 的教材 “Probability: Theory and Examples”。这本书的好处我就不再介绍了，院长陈大岳老师在世图影印版的前言中已经夸了一遍。我个人的体会是，Durrett 的书在讲解证明的时候非常简练，很少写为什么要这样证，我有时候读了半天也没搞明白思路。Birkhoff 遍历定理算是其中一个，于是我重新整理了一下书中的证明，作此文留念。
Birkhoff 遍历定理最初由 Birkhoff 本人在 1931 年发表，原文长达 50 页。随后在 1939 年 K.Yosida （吉田耕作） 和 S.Kakutani （角谷） 利用极大遍历定理给出了一个 10 页的简洁证明，不过他们关于极大遍历定理的证明还是啰嗦了点，后来 Garsia 给出了极大遍历定理的一个仅有寥寥数行的惊人证明，这也是当前大多数教材采用的途径，本文就来介绍这一证明。
问题： 假设你是一位大龄男士，准备参加 100 场相亲 （别介意具体数字）。你打算依次与每个女士 \(i\) 约会，然后根据印象给她打一个分数 \(X_i\)，\(X_i\) 的值介于 \([0,1]\) 之间。如果你对女士 \(i\) 很满意，那么就和她结婚，否则就放弃她，参加下一场相亲，当然拒绝了人家可就没有回头的机会了。如果你拒绝了前 99 位女士，那么不论第 100 次相亲结果如何你都只能和最后这位女士结婚。在相亲之前，你对这些女士的情况一无所知，所以姑且假定她们的分数 \(X_i\) 都是 \([0,1]\) 上均匀分布的独立的随机变量。问题是：应该采取怎样的相亲策略，才能娶到你最中意的女士？
今天的问题是群表示论在物理中的一个小应用：
问题： 平面上有三个质量均为 \(m\) 的质点 \(A,B,C\)，它们位于正三角形的三个顶点。质点之间两两由弹簧相连，三个弹簧完全一样。弹簧质量忽略不计。
初始时所有质点都处于静止状态，弹簧之间没有张力。假设给这三个质点分别施加一个初始速度，使这三个质点在平面内作刚体运动，不考虑任何摩擦力和空气阻力，那么这个系统的简正模式 (normal mode) 是什么？
这里 简正模式 的含义是所有质点按照一个共同的频率和固定的相位关系相对于各自的平衡位置作简谐振动。
当前网速较慢或者你使用的浏览器不支持博客特定功能，请尝试刷新或换用Chrome、Firefox等现代浏览器