这是一个关于二维随机游动的小系列，整理自我研究生时的读书笔记，每篇文章会从一个有趣直观的问题出发，介绍随机游动理论中的一个相关知识。整个系列的内容都比较基础，涉及的知识在 Durrett 的教材 ¹ 中都可以找到。

今天的问题依然有趣，但是并不简单。

问题：假设某醉汉以太阳系的中心为原点出发，在一个固定的平面内，以恒为 1 米的步长作随机行走。每次醉汉等概率地随机选择东、南、西、北中任一方向，然后向此方向移动 1 米的距离。如果某个时刻醉汉回到了原点，或者离开了太阳系则过程结束。

现在有 A, B 两个旁观者打赌哪一种情形先发生，A 认为醉汉会先回到原点，B 认为醉汉会先离开太阳系。请问 A, B 获胜的概率分别是多少？

作为参考，太阳系半径约为 45 亿千米，看作一个中心在原点的圆形区域。

The English version of this doc is here.

本文要介绍的是我写的一个高颜值的、脱离了低级趣味的小程序：用 Python 和 POV-Ray 绘制各种三维多面体和四维多胞体，代码在 github 上。

以下是用这个程序渲染的一些例子，其中不同颜色的顶点/边/面表示它们在对称群的作用下位于不同的轨道中，具体解释见后。

2021/06/27 更新：我更新了一下 shader 代码，把每个动画放在一个 SVG 图片中。最后几个动画代码是可以使用键盘选择场景的，具体操作如下：

• 按下 1 开启/关闭 Möbius 变换。
• 按下 2 开启/关闭椭圆旋转。
• 按下 3 开启/关闭双曲缩放。
• 按下 4 开启/关闭展示 Riemann 球面。

这几个按键可以组合出许多不同的效果来！

本文的想法源自 Roice Nelson 的 shadertoy 项目，我觉得他的创意很棒，就是效果有点糙，于是动手改进了一番。不懂的人看这个动画可能只是觉得好玩，其实它背后的数学并不简单。

这篇文章将用动画的形式从三个角度演示 Möbius 变换，这三个角度是密切相关的：

1. Möbius 变换作为扩充复平面 \(\hat{\mathbb{C}}\) 到自身的全纯函数。
2. Möbius 变换作为 Riemann 球面 \(S^2\) 到自身的全纯函数。
3. Möbius 变换作为上半双曲空间中的等距变换。

本文只做演示，并不介绍详细的数学证明。读者可以参考下面的资料：

1. 维基百科页面.
2. Visual complex analysis, Tristan Needham.
3. Indra's pearls, chapter 3.

本文的动画应该可以帮助你更好地理解这些资料中的内容。

本文要介绍的是我写的一个有趣的 Python 小程序，一个脱离了低级趣味的程序，一个有益于广大人民了解算法的程序。代码在 Github 上。

这个程序可以用来制作各种各样的算法动画，包含但不限于：

几年前在知乎上有这么 一个问题：

问题：有哪些 \(\mathbb{Z}[x]\) 中的多项式，它们在有理数域 \(\mathbb{Q}\) 上是不可约的，而对任意素数 \(p\)，模 \(p\) 以后在 \(\mathbb{Z}_p[x]\) 上都是可约的？

当时我给了回答，后来账号注销了，答案也就一并删除了。现在把我的原答案贴在这里：

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

本文的代码在 Github 上。

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

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

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

请问：用边长为 1 的菱形密铺它，有多少种不同的方法？

前言

你可能经常听到这样一句话：“做数学要大胆假设，小心求证”。我们今天要介绍的故事主角平面分拆中的 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-\) 二项式定理作为工具，所以计算步骤会显得有些繁琐。

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

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

如果你对李代数有所了解的话，相信很大概率你会见过下面的图案：（参考维基百科的 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 本人在 1931 年发表，原文长达 50 页。随后在 1939 年 K.Yosida （吉田耕作） 和 S.Kakutani （角谷） 利用极大遍历定理给出了一个 10 页的简洁证明，不过他们关于极大遍历定理的证明还是啰嗦了点，后来 Garsia 给出了极大遍历定理的一个仅有寥寥数行的惊人证明，这也是当前大多数教材采用的途径，本文就来介绍这一证明。