绿巨人走迷宫的游戏，芒种，花园

一处小径分叉的花园，一座谁都走不出来的迷宫，一本谁也看不懂的天书，一场生死攸关的赌博，一次充满悔恨的谋杀，一个随心所欲的游戏，本篇文章将和大家聊聊博尔赫斯的小说《小径分叉的花园》《赫伯特奎因作品分析》，以及它们和数学概念鞅的联系。

注：本篇部分内容来自作者之前的文章《颔疆》（作者的话：致敬博尔赫斯），以下内容涉及博尔赫斯小说的部分剧透，请谨慎阅读。

豪尔赫·路易斯·博尔赫斯（Jorge Luis Borges ，1899年8月24日-1986年6月14日）是阿根廷诗人、小说家、散文家兼翻译家。

豪尔赫·路易斯·博尔赫斯

图源：网络

我想很多人和我一样，最早读过的博尔赫斯作品就是来自语文读本上的《小径分叉的花园》[1]。该小说讲述了青岛大学前英语教师余准博士的一场逃亡之旅。在逃亡中，余准遇到汉学家斯蒂芬艾伯特博士，参观了一座小径分叉的花园，并因此得知了自己曾祖父彭㝡的秘密。以下截取小说原文：

彭㝡是云南总督，他辞去了高官厚禄，一心想写一部比《红楼梦》人物更多的小说，建造一个谁都走不出来的迷宫。他在这些庞杂的工作上花了十三年工夫，但是一个外来的人刺杀了他，他的小说像部天书，他的迷宫也无人发现。我在英国的树下思索着那个失落的迷宫：我想象它在一个秘密的山峰上原封未动，被稻田埋没或者淹在水下，我想象它广阔无比，不仅是一些八角凉亭和通幽曲径，而是由河川、省份和王国组成……我想象出一个由迷宫组成的迷宫，一个错综复杂、生生不息的迷宫，包罗过去和将来，在某种意义上甚至牵涉到别的星球。我沉浸在这种虚幻的想象中，忘掉了自己被追捕的处境。在一段不明确的时间里，我觉得自己抽象地领悟了这个世界。

彭㝡所书写的这本书被后人称作为“一堆自相矛盾的草稿的汇编”，而建造的迷宫也“无人发现”，在汉学家斯蒂芬艾伯特博士为余准揭露天书与迷宫的秘密之前，让我们先来聊聊数学概念鞅[2]。

注：鞅的另一个含义是套在马颈或马腹上的皮带，我们之后也来谈谈该含义和数学鞅的关系。

鞅（Martingale）

非正式定义：E[未来] = 现在

考虑一个赌徒问题：一个赌徒的初始资产为零，第一轮赌博结束后，她有一半的机率获得1元，一半的机率输1元；第二轮赌博结束后，她有一半的机率获得3元，一半的机率输3元。

那么赌徒对未来资产的期望一定等于她现在的资产值。具体来说，记赌徒初始资产为 X0=0，第一轮结束后资产 X1可能的结果为1或-1。第二轮结束后资产为X2，当赌徒第一轮赢了，X2可能的结果为4或-2；当赌徒第一轮输了，X2可能的结果为2或-4：

E[X1] = X0, E[X2｜第一轮结果] = X1

注：E[X] 为随机变量 X 的期望。

这里赌徒时刻0，1，2的资产分别为 X0，X1，X2，其组成了一个随机序列，也是一个最简单的鞅。

鞅中的随机性 & 多叉平行宇宙

当我们计算第一轮赌博结束时的资产期望时，其随机性来源于第一轮的赌博结果，当第一轮结束后，计算第二轮结束时的资产期望时，其随机性来源于第二轮的赌博结果。

考虑我们生活在一个离散的宇宙，把未来所有的可能性展开，我们就得到一个多叉树，或者多叉平行宇宙，每一个时刻的分叉，可以认为来源于人的决策，也可以认为来源于命运的选择。

给定多叉平行宇宙，给定任意事件（赌徒最终的资产，余准是否完成任务），在所有时刻对该事件的期望将会组成一个随机序列。我们称该随机序列为 Doob 鞅，并可以证明它每一刻都满足

E[下一刻的未来] = 现在

注：在正式定义中，多叉平行宇宙可以由 sigma 代数和 Filter 来刻画，大家可以参考相关 lecture note[2]。

回溯（Backward Induction）

如果多叉树可以有最终的节点，即宇宙的终极，末节点一定可以确定我们关心的事件，它所对应的 Doob 鞅可以从后往前定义，只要每一个时刻的分叉可以满足

E[下一刻的未来] = 现在

因此在鞅的定义里，比起从现在看向未来，我更倾向从未来回溯现在。

最后我们来探讨一下骑马和数学鞅的关系，据说是因为通过马具鞅，可以让马头下一刻位置的期望是此刻的位置[3,4]。

《小径分叉的花园》

回到博尔赫斯的小说，我想大家已经隐约猜到那本天书和迷宫到底是什么了。斯蒂芬艾伯特博士递给余准一张薄纸，上面有余准曾祖父彭㝡的笔迹：

彭㝡一手好字名不虚传。我热切然而不甚了了地看着我一个先辈用蝇头小楷写的字：我将小径分岔的花园留诸若干后世（并非所有后世） 。

艾伯特明确地说道：

小径分岔的花园是彭㝡心目中宇宙的不完整然而绝非虚假的形象。您的祖先和牛顿、叔本华不同的地方是他认为时间没有同一性和绝对性。他认为时间有无数系列，背离的、汇合的和平行的时间织成一张不断增长、错综复杂的网。由互相靠拢、分歧、交错或者永远互不干扰的时间织成的网络包含了所有的可能性。在大部分时间里，我们并不存在；在某些时间，有你而没有我；在另一些时间，有我而没有你；再有一些时间，你我都存在。目前这个时刻，偶然的机会使您光临舍间；在另一个时刻，您穿过花园，发现我已死去；再在另一个时刻，我说着目前所说的话，不过我是个错误，是个幽灵。

没错，博尔赫斯用了一个他常用的技巧，表面在谈空间，实际谈的是时间。天书就是迷宫，也是花园，而这些错综复杂，不断增长的网正对应前文赌博例子中的二叉树图，也就是多叉平行宇宙。

虽然在小说里并没有 E[未来]=现在 的概念，但是我们很容易在这座花园里定义出鞅：

小说里余准也在面临一场生死攸关的“赌博”，他在逃亡过程中一直藏着一个秘密的任务，他的结局无非两种，要么在完成任务前被抓，要么成功完成任务。而逃亡的过程有太多的随机性，那么在他逃亡过程中对任务最终是否能成功的期望就是一个 Doob 鞅。至于这样的 Doob 鞅能有什么样的应用，我们谈完博尔赫斯的另一篇小说后再回来谈谈。

《赫伯特奎因作品分析》

与《小径分叉的花园》不同，这篇小说一开始读来有些让人摸不着头脑。博尔赫斯采用了他常用的虚拟书评风格：虚构了一个作家赫伯特奎因，并虚构在该作家死后评点他那些具有实验性质的作品，以下摘取自原文[1]：

更邪门的是那本名为《四月三月》的逆行枝蔓的小说……评判小说时，谁都发现那是一场游戏，……《四月三月》里的世界不是倒退的，倒退的只是叙事的方式。正如我上文所说，逆行枝蔓。全书共十六章。第一章讲的是几个互不认识的人在人行道上含糊不清地交谈。第二章讲的是第一章前夕的事。第三章也是逆行的，讲的是第一章另一个可能的前夕的事情……

他还在书中画了示意图：

看起来和前文提到的多叉平行宇宙类似，但虚构小说《四月三月》的结构和前文的多叉平行宇宙有一个本质区别：

《四月三月》里从现在 x 开始倒退，倒退到多个过去 y1，y2，y3，再分别从 y1，y2，y3 倒退到多个过去。因此，这里是有一个现在和多个可能的过去。而鞅中需要的多叉平行宇宙恰恰相反，是有一个现在和多个可能的未来。

逆鞅（Reverse Martingale）

因此，《四月三月》事实上可以对应另一个有意思的概念，逆鞅[5]。当然《赫伯特奎因作品分析》里面提《四月三月》的重点是“游戏”，“对称，随心所欲，厌倦”，本质上是为逆鞅提供了一个多叉逆平行宇宙，并没有 E[过去]=现在 的概念，正如《小径分叉的花园》里也没有 E[未来]=现在 的概念，但是不可否认，《小径分叉的花园》和《赫伯特奎因作品分析》是两篇非常有趣，蕴含数学、计算机思想的小说。

鞅的应用

谈完小说，我们来谈谈鞅的应用，尤其是在计算机领域里分析随机变量集中性以及收敛时间的应用。

Azuma 不等式

这是鞅最重要的应用之一。本质上，其刻画了未来有多符合现在的期望。以前文赌博为例，如果赌徒可以一直赌下去，且每一轮都有一半的几率赢 x 元，一半的几率输 x 元，那么第100轮她的资产的期望仍然是零，而她第100轮真正的资产和期望有多远就可以用 Azuma 不等式和每轮资产变化的上界刻画。每轮资产变化的上界越小，真正的资产会更集中于期望。当然这个问题可以直接利用 Chernoff bound 来做，因为资产可以写成独立随机变量求和的形式，但 Azuma 不等式可以应用在更复杂的，无法写成独立随机变量求和形式的随机变量分析，例如用作分析快排（quick sort）实际花费时间有多符合它的期望花费时间。

Optional Stopping 定理

赌徒或者余准可以根据一个停止法则停下来。例如赌徒进行多轮赌博，每一次都以一半机率赢1元，一半机率输1元，赌徒要么赚200元收手，要么输100元收手，余准要么在任务完成前被抓住，要么被抓住前完成任务。

在我们确定一个停止法则后，Optional Stopping 定理表明满足某些条件后，停下来的时间 T 对应的 XT 的期望仍然是 X0。这并不显然，因为 T 也是个随机变量。在 X0 容易计算的情况下，例如前文赌博的场景 X0=0，可以用来分析赌徒停下来时赚200元/输100元的机率。

Optional Stopping 定理也可以用来分析停止时间的期望上界，以余准为例，如果余准在逃亡过程中对自己最终是否能完成任务的期望高概率波动很大，那么他会很快停下来。这个分析主要基于平方期望 E[(Xt)^2] 关于 t 的单调性，同样的分析方法也可以用来分析两个理性人需要花多长时间达成共识。

至于余准停下来时到底有没有完成任务，那令人悔恨莫及的谋杀到底是什么，这里我就不往下剧透了，欢迎感兴趣的读者读读原文。

注：以上应用可以具体参考 lecture note[2]

麦金太尔街1844号

最后我们再回来谈谈小说，我有一个目标，在十分缓慢地进行中。这个目标就是把我自己课上提到的有意思的概念小说化，在2021年的时候，我就想写一篇和鞅有关的小说，不过一直没有好的想法。

这学期我又一次讲到鞅，在我随手翻了《赫伯特奎因作品分析》后，立马构思了《颔疆》这篇小说，并模仿了利用小说结构来“玩”的思想。有意思的是博尔赫斯在文中“嘲讽”了我这样的模仿者：

《四月三月》出版后，奎因后悔不该用三元次序，他预言说仿效他的人会用二元次序。

那是自然，二叉树能讲清楚的东西当然没必要用三叉树，欢迎感兴趣的读者阅读这篇小说。

最后，希望大家可以永远漫步在小径无限分叉的花园里！

Reference:

[1] 豪尔赫·路易斯·博尔赫斯（Jorge Luis Borges），小径分岔的花园（博尔赫斯全集Vol.1）

[2] CS271 Randomness & Computation, Alistair Sinclair, https://people.eecs.berkeley.edu/~sinclair/cs271/n18.pdf

[3] Roger Mansuy, The Origins of the Word “Martingale”

[4] https://www.zhihu.com/question/22018073

[5] https://faculty.math.illinois.edu/~psdey/MATH561SP21/week14.pdf

图文 | 孔雨晴