二维随机游动 (二):一个随机的完美迷宫分别有多少死角、拐角、岔路和路口?

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

问题:在 \(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 米的步长作随机行走。每次这个人等概率地随机选择东、南、西、北中任一方向,然后向此方向移动 1 米的距离。如果某个时刻此人回到了原点,或者离开了太阳系则过程结束。

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

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

Coxeter 群,有限状态机与均匀密铺

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

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

例子

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

Todd-Coxeter 算法和 3D/4D 均匀多胞体

The English version of this doc is here.

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

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

Möbius 变换的分类与上半双曲空间的等距

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 上。

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 特征公式

2022/06/24 更新:在本文写作十余年之后,我回顾了下这个博客里的旧文,有一点感想写在这里。

我的博客文章大体是这样的:自己以为洋洋洒洒讲清楚了,其实并没有。因为离开数学圈以后我的知识已经不再更新了 (或者更新的很慢了),也没有得到过读者的反馈,所以文章几乎没有优化和改进。

其次从技术写作的角度看这也是一篇很糟糕的文章 (英文有个词形容叫 horrible),理由是:

  1. 前面 90% 的内容都极其抽象晦涩,介绍了一个又一个定理,但最后只用了 10% 的篇幅算了 \(\mathfrak{sl}_3(\mathbb{C})\)\(\mathfrak{sl}_n(\mathbb{C})\) 的例子。这其实和真正理解数学的逻辑是反过来的:一个学习者应该熟悉 10 个例子,从中归纳出 1-3 个定理,然后在验证定理的证明以后放心地忘记它们。而不是学了一大堆名词以后一个例子也磕磕巴巴举不出来。
  2. 本文可能只适合正在念 Humphreys 的教材,并且正好卡在第六章表示论这一章上的同学。这里一开头就罗列了一大堆书中前五章的结论,然后直接从最高权表示开始,所以采用其它学习途径的同学恐怕会不太习惯。我当然也很想有更多启发性的叙述,但我的水平仅限于字面意义的理解证明。我尽量在每一段证明之前给出它的动机,如果你正在啃 Weyl 特征公式的证明,并且不太习惯其它地方的表述的话,这里可能帮到你。

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

 | 

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