周末刚完成了一个有点烧脑的 Shadertoy 项目，Escher 风格的非周期密铺：

和之前一样，我们还是通过一个有趣的问题来引入主题。

问题：在 \(n\times n\) 的正方形网格图 \(G_n\) 的所有生成树中等概率地随机任选一个，记这个随机生成树为 \(T\)，\(T\) 叫做 \(G_n\) 的一个均匀生成树。对 \(G_n\) 中任一顶点 \(v\)，\(v\) 是 \(T\) 的叶节点的概率是多少？

这个问题可以换一种更通俗的描述：

等价问题：对一个完全随机的 \(n\times n\) 的完美迷宫，它包含的“死角”的比例是多少？

为什么这两个问题是一回事？

一个迷宫称作是完美的，如果迷宫中的任何两个房间之间都有且仅有唯一的道路相连，这正是生成树的等价描述！迷宫中的一个房间称作是“死角”，当且仅当它只有一条道路与其它房间相通，没有其它出路，这正是叶节点的等价描述！

下图显示了三个不同的均匀生成树，它们分别来自大小为 \(80\times 80\)，\(120\times120\) 和 \(200\times200\) 的三个网格图，这三个生成树的叶节点 (用蓝色标出) 占全体顶点的比例分别为 \(1884/6400=0.294375\)，\(4234/14400\approx0.294028\)，\(11776/40000=0.2944\)。咦？看起来好像是在围着一个固定的值波动喔？

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

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

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

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

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

终于完成了一个新的 Python 小程序，虽然还有一些功能有待实现，但是大致的效果已经出来了。这个程序是我最近半年多来利用几乎所有业余时间呕心沥血、披星戴月、艰苦攻关完成的新作品，是一个纯粹的、优雅的、有益于广大人民欣赏数学之美的程序。代码在 github 上，目前还有许多不尽人意的地方，后面还会继续维护和改进。

这个程序是我目前为止写过的所有程序中最难的一个，它涉及的数学知识相当复杂，使用了 Coxeter 群的一些深刻性质，所以理解起来可能不太容易。但是这个程序可以做的事情相当惊人，它可以用来绘制二维和三维欧式空间、双曲空间和球面上的各种均匀密铺 (uniform tilings)，生成的图片效果非常优美。我最好还是先有图有真相：

例子

• 下图是二维的欧式密铺 omnitruncated (4, 2, 4)：

  

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.

其中我特别推荐 Indra's pearls 一书。借助本文的动画你可以很容易地理解这些资料中的内容。

文中的动画全部使用 shader 程序制作，代码在 github 上。

本文要介绍的是我写的一个有趣的 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-\) 二项式定理作为工具，所以计算步骤会显得有些繁琐。