AA还是AK——又一个违反直觉的概率问题

不论是孩子，还是成人，看到下面这个问题一定会有一个出于直觉的答案：

假设我们有一副完整的、由52张数字或字母牌以及2张大小王组成的扑克牌，将这54张牌洗好，然后从上到下一张一张地翻开，直到出现第一张A（可以是任意花色），请问紧接着的下一张牌出现黑桃A的概率大，还是出现红桃K的概率大？

你直觉中的答案是什么？

我的直觉告诉我：红桃K出现的概率更大一些。为什么呢？因为，

当第一张A不是黑桃A时（第一种情况），黑桃A和红桃A紧接着第一张A出现的概率是相等的；当第一张A恰好是黑桃A时（第二种情况），显然不会再出现一张黑桃A，只可能出现红桃K。所以，综合起来红桃K出现的概率更大。

很可惜，我们又一次落入了直觉的陷阱。

这个问题正确的回答是：两者出现的概率是相等的。

What?

先解释一下，为啥两张牌出现在第一张A后面的概率是相等的。为了方便解释，我们将黑桃A紧接着第一张A出现的情况称为AA，将红桃K紧接着第一张A出现的情况称为AK。

首先我们考虑AA出现的概率。一副牌的任意一种排列，即任意洗牌后54张牌可能出现的一种顺序，可以理解成：先洗好除黑桃A之外的53张牌，然后将黑桃A插入到牌堆中，即或者在两张牌之间，或者在第1张牌之前，或者在第53张牌之后，所以黑桃A一共有54个不同的可能插入位置。

在这54种可能中，只有当黑桃A插入到紧接着从上到下的第一张A后面的那个位置时，才会出现AA的情况。同时，因为对于53张牌的任意一个排列，黑桃A可能的插入位置都有54个，而AA出现的情况都有且只有1次。因此，对于54张牌的一共 54! 种排列，AA出现的概率等于1/54。

其次我们考虑AK出现的概率。同样地，考虑先洗好除红桃K之外的53张牌，然后将红桃K插入到这53张牌的牌堆中。我们可以发现，以上对黑桃A的分析完全适用于红桃K，所以类似地，对于54张牌的一共 54! 种排列，AK出现的概率也等于1/54。

因此，AA和AK出现的概率相等。

有读者可能要挠头了：这么解释对是对，但我们的直觉看上去也是对的啊！问题出在哪里？

实际上，我们的直觉只有在第二种情况中是正确的，即：当第一张A恰好是黑桃A时，显然不会再出现第二张黑桃A，这种情况下AA不可能出现，只可能出现AK。所以在这种情况下，AK出现的概率要大于AA出现的概率。

但是，我们的直觉在第一种情况中是错误的，即：实际上，当第一张A不是黑桃A时，AA和AK出现的概率是不等的。具体来说，在第一种情况中，AA出现的概率要大于AK出现的概率。两种情况综合考虑，AA和AK出现的概率恰好相等。

假设我们把黑桃A和红桃K挑出来，先洗好剩下的52张牌，然后把它们一一翻开，确定第一张A的位置。不失一般性，假设第一张A是方块A，方块A之前有a张牌，之后有51 – a张牌，这样一共有52张牌。注意，0 ≤ a ≤ 49，因为方块A是第一张A，红桃A和草花A必须排在它后面，所以它前面最多有49张牌。

现在，考虑在这52张牌的牌堆中插入黑桃A。因为要保持方块A是第一张A（否则就属于第二种情况了），所以黑桃A只能排在方块A之后，这样一共有52 – a个可能的位置。其中，当且仅当黑桃A在紧接着方块A的位置上时才会出现AA，所以对于这53张牌，其中出现AA的概率为1/(52 – a)。

然后，考虑在这53张牌的牌堆中插入红桃K。显然，红桃A插入到任何位置都不会改变方块A是第一张A的条件，所以红桃A一共有54个可能的插入位置，其中插入到紧接着方块A的位置上时才会出现AK，所以对于所有54张牌的排列，其中出现AK的概率为1/54。

结合上一步中AA出现的情况，其中也有1/54的概率从AA转变成了AK，即红桃K恰好插入到了方块A和黑桃A之间，所以对于最后所有54张牌的排列来说，出现AA的概率为：

1/(52 – a)∙(1 – 1/54) = 53/(52 – a)∙(1/54)

因为0 ≤ a，所以必然有：53 > (52 – a)。

因此在第一种情况中，出现AA的概率一定大于(1/54)，即在第1张A不是黑桃A的情况下，出现AA的概率必然大于出现AK的概率。

以上，证明了关于第一种情况，我们的直觉是错误的，因为我们忽略了需要满足第一张A不是黑桃A的限制条件。

一个名为“猪”的骰子游戏

这个游戏之所以名为猪（Game of Pig），也许是因为游戏规则比较简单，而不是因为玩这个游戏不用动脑子。

在长途火车上，在候诊时间中，抑或是一个无聊的午后，只需要一个六面骰子、一支笔和一张纸，两个人就可以通过玩这个简单的游戏来打发时间。

游戏的规则是这样的：

两个玩家轮流掷骰子。游戏开始时，两个玩家的累计分数均为0；游戏开始后，累计分数最先达到或者超过100分的玩家获胜。

在玩家的每个轮次中，如果他掷出

• 点数1，那么他在本轮次中的累积点数清零，并结束本轮次；
• 其他点数，那么先将这个点数加入他在本轮次中的累积点数，然后他可以选择继续掷骰子，或者结束本轮次。

轮次结束后，玩家在本轮次中得到的累积点数计入他的累计分数。然后，轮到另一个玩家开始他的轮次。

比如，玩家A在某一轮次中依次掷出了3，2，6点，本轮次累积点数为11点。他可以选择就此结束，这样这11点将被计入他的累计分数，“落袋为安”。他也可以选择进行第4次投掷，如果这一次掷出1，那么累积点数清零，本轮次结束，累计分数不变；如果这一次掷出5，那么累积点数变成15点，他可以又一次选择就此结束还是继续。

这个游戏在策略上有一点点像黑杰克或者21点：每次投掷后玩家都有一个选择，是继续博更多的点数，还是见好就收，落袋为安。

如果我们不考虑两个玩家之间的博弈，也不考虑不同的局面下应该采取的不同策略，纯粹考虑游戏规则下多次投掷带来的点数的数学期望，那么可以初步得出一个最优的投掷次数。

对于每一次投掷，玩家有1/6的概率失去所有的累积点数，也有1/6的概率分别得到2、3、4、5和6点，后面这5个点数的平均值为4。因此我们可以简单地认为，

每一次投掷，玩家的累积点数有1/6的概率被清零，也有5/6的概率增加4点。

因此，1次投掷后，玩家的累积点数的数学期望为(5/6)∙4。

在第2次投掷中，1/6的概率下累积点数清零，5/6的概率下累积点数增加4，玩家在2次投掷后得到8点的概率为(5/6)²。

因此，2次投掷后，玩家的累积点数的数学期望为(5/6)²∙(2∙4)。

……

一般性，在n次投掷后，玩家的累积点数的数学期望E(n) = (5/6)ⁿ∙(4n)。

简单求一下导数，dE(n)/dn = 4(5/6)ⁿ + ln(5/6)∙(5/6)ⁿ∙(4n) = 0。

得到n = 1/ln(6/5) ≈ 5.5。

n约为5.5时，累积点数的数学期望取最大值。换句话说，在玩家连续投掷了5 – 6次、累积点数达到20 – 24点，此时见好就收、落袋为安是玩家的最佳选择。

以上对数学期望的计算没有考虑到不同的局面，在现实中，不同局面下玩家有不同的选择是再正常不过了。

比如，如果玩家A的累计分数已经达到99分，玩家B的累计分数只有75分，而此时正处于玩家B的轮次中，玩家B本轮次已经投掷了6次，累积点数达到了23点。

如果根据以上数学期望的计算，玩家B应该选择结束本轮，那么他的累计分数将达到98分。玩家A开始他的轮次，有5/6的概率得到至少2点，直接兑现后从而获胜。

反之，如果玩家B采用更为激进一些的策略，选择继续投掷，那么他同样有5/6的概率得到至少2点，兑现后他的累计分数恰好不小于100分，玩家B成为获胜者。

因此在这种情况下，玩家B应该选择继续投掷。

总体上来说，在游戏开始之初，因为大家离100分的目标都较远，此时应该采取投掷5 – 6次就主动结束的策略；随着游戏的进行，双方的分数越来越接近100分，此时应该采取更为激进一些的策略，即不妨变得更为贪心，选择更多次数的投掷。

如果再考虑到游戏中的另一个玩家也根据局面、甚至根据对手的策略来选择最佳策略，这个问题就变得更加复杂起来。

计算机科学家托德·内勒 （Todd W. Neller）编写了一个程序用来计算两人游戏中所有相关的概率^【1】。令人惊讶的是，游戏的最佳策略呈现出非常复杂的波浪结构，且这种结构并不如人们想象中那么平滑。

上图中，水平面上的两个坐标轴表示两个玩家的累计分数，即游戏过程中的某个局面；垂直坐标表示轮次中的最佳投掷次数。

根据内勒的计算，如果两名玩家都采取最佳策略，那么首先开始游戏的玩家略微占优，其获胜的概率为53%。如果首先开始游戏的玩家采取最优策略，而第二个玩家始终采用5 – 6次投掷的策略，那么首先开始游戏的玩家的获胜概率为58.7%。相反，如果首先开始游戏的玩家始终采用5 – 6次投掷的策略，而第二个玩家采取最优策略，那么首先开始游戏的玩家的获胜概率只有47.8%。

参考出处：

1. http://cs.gettysburg.edu/projects/pig/index.html

喝醉的蜜蜂与随机游走（下）

在本文的中篇^【1】中，我们简单了解了二维网格尤其是正方形网格的随机游走。正方形网格是二维网格中最简单的一种，两个维度相互正交且独立，所以我们可以通过分步计数的方法得到随机游走概率分步的表达式。在本文的余下部分，我们将了解到其它两种不同类型的二维网格上的随机游走。

事实上，除了正方形网格以外，根据网格点之间的连接以及网格的形状不同二维网格还可分为很多种，其中有一大类被称为“阿基米德网格”（Archimedean Lattices），在物理和化学中阿基米德网格常常被用来研究晶体中原子排列的规律，所以它们也被称为“阿基米德晶格”。

早在古希腊时期，亚里士多德和阿基米德等先哲就已经对多边形的网格和平面铺砌做出过深入的研究，阿基米德对多边形网格的构成加上了两个条件：1. 网格中的每个网格（即空洞部分）都必须为正多边形；2. 网格中的每个顶点（即边和边的连接点）都被同样序列的多边形包围。

根据这两个条件，阿基米德发现了11种网格，这11种网格后来被称为“阿基米德网格”。

每一种阿基米德网格都有一个特殊的标注，它表示包围每一个顶点的多边形的序列。比如上图中的正方形网格标注为(4⁴)，表示每个顶点被4个正方形所包围；而在上图左下方的那个网格中，每个顶点顺序地被2个正三角形，1个正方形，1个正三角形和1个正方形所包围，所以其标注为(3², 4, 3, 4)，该标注严格地描述了这5个多边形围绕每一个顶点的顺序，所以不能简单地将它合并为(3³, 4²)。

在11种阿基米德网格中，只有3种网格由单一的多边形组成（即标注中只有1项），它们是正方形网格(4⁴)，正三角形网格(3⁶)，和蜂巢形状的正六边形网格(6³)。

下面，我们简单地了解一下正三角形网格和正六边形网格上的随机游走。

观察正三角形网格上的每一个顶点，可以得知它与周边的6个顶点相连，在随机游走中，质子去往6个相邻顶点的概率都为1/6。这看上去似乎和三维立方体随机游走相同，但如果我们进一步观察两种网格顶点的连接方式，就会发现在二维正三角形网格中，6个相邻顶点两两相连（绿色实线箭头），而在三维立方体网格中，6个相邻顶点之间是孤立的（红色虚线箭头）。

因此，我们不能简单地将三维立方体网格上的随机游走模型套用在二维正三角形网格上。

尽管如此，这个对比仍然给了我们一个启发：是不是可以将正三角形网格转换成一个顶点之间带有额外连接的正方形网格？如果我们把正三角形网格在水平方向上向左拉动，使得原来与水平方向呈60°夹角的网格线垂直于水平方向，那么我们就可以得到如下的一个正方形网格，这个网格中的任意一个顶点除了上下左右四个相邻顶点以外，它还和左上方和右下方两个顶点之间通过对角线相邻。

实际上，我们并不需要将网格拉成90°夹角，把正三角形网格变形成正方形网格；而只需将正三角形网格中的水平方向定义为x轴，与水平方向呈60°夹角的网格线定义为y轴，这样，正三角形网格上的任意一个顶点都将被一个、且只被一个二维坐标(x, y)所定义。比如下图中A点的坐标为(2, 3)。

从原点O出发，n步随机游走之后达到坐标(x, y)的概率P(n, x, y)就可以用以下递推公式表示：

P(n, x, y) = P(n – 1, x – 1, y + 1)/6 + P(n – 1, x – 1, y)/6 + P(n – 1, x, y – 1)/6 + P(n – 1, x + 1, y + 1)/6 + P(n – 1, x + 1, y)/6 + P(n – 1, x, y + 1)/6

有了递推公式以及初始条件P(0, 0, 0) = 1，我们就可以通过编程利用迭代计算得出P(n, x, y)。

那么，有没有可能仍然使用计数的方法来解决这个问题呢？答案是肯定的。

考虑原点O的6个相邻顶点，假设它们到O的距离为1，那么这6个顶点都位于以O为圆心的单位圆上。如果将这个二维平面视为复平面，那么从实数轴出发、逆时针数，原点到这6个顶点的向量依次对应于1，-ω²，ω，-1，ω²和- ω，其中ω = e^iπ/3。在正三角形网格随机游走中，质子的任意一步都可以用这6个向量之一来表示：{1, -ω², ω, -1, ω², – ω}。因此，从O到A的任一路径都可以表示为这6个向量的线性组合。

进一步考虑到这6个向量以相反数成对出现，我们可以定义{1, ω, ω²}为基本向量集合，从O到A的任一路径都可以表示为这3个基本向量的线性组合。

比如在上图中，路径1可以写作(2, 0, -3)，对应于(1, ω, ω²)∙(2, 0, -3)，即2 – 3ω²。对应的路径长度n = 5。

路径2可以写作(5, 3, 0)，对应于(1, ω, ω²)∙(5, 3, 0)，即5 + 3ω。对应的路径长度n = 8。

路径3可以写作(0, -2, -5)，对应于(1, ω, ω²)∙(0, -2, -5)，即-2ω – 5ω²。对应的路径长度n = 7。

此外，考虑到恒等式1 + ω + ω² = 0，我们还可以发现以上三个式子是等价的：

2 – 3ω² = 5 + 3ω + 3(1 + ω + ω²) = -2ω – 5ω² + 2(1 + ω + ω²)

同时，考虑到每一个基本向量都有正负两个方向，加入一对同一基本向量的正负向量对路径没有影响。

所以，对于该复平面上任意一个点A，如果已知从O到A的某一条路径(x₀, y₀, z₀)，那么从O到A的所有其它路径(x, y, z)都可以用以下公式表示：

(1, ω, ω²)∙(x, y, z) = (1, ω, ω²)∙(x₀, y₀, z₀) + q(1 + ω + ω²) + r(1 – 1) + s(ω – ω) + t(ω² – ω²)

其中q、r、s、t为整数。

从上式可以看出，对于从O到A的任意两条路径，其差别要么发生在某一个基本向量上（对应于增加或者减少一对同一基本向量的正负向量），称为单向量变化，要么发生在全部三个基本向量上（对应于增加或者减少一组1 + ω + ω²），称为三向量变化，但其差别不可能发生、且仅仅发生在两个基本向量上。

我们暂时忽略单向量变化，如果固定某一条路径中的某一个基本向量不变，那么其它两个基本向量也不会发生变化。我们把这种路径称为基本路径。

首先，因为每个基本向量都具有结合律，所以每条基本路径实际上都代表着一组路径。以路径2为例，它代表着所有以5个基本向量1和3个基本向量ω组成的路径，比如1 + 1 + 1 + 1 + 1 + ω + ω + ω，或者1 + ω + 1 + 1 + ω + 1 + 1都可以用(5, 3, 0)表示，这种因为不同顺序形成的路径数等同于组合数C(8, 5)∙C(3, 3)，即先从8步中分配5步给基本向量1，再从剩下3步中分配3步给基本向量ω。

其次，考虑单向量变化，每一条基本路径上在路径中加上任意多对相反的基本向量。比如(5, 3, 0)可以表示为5 + 3ω + r(1 – 1) + s(ω – ω) + t(ω² – ω²)。

基于基本路径的这两个特点，我们发现从O到A、沿着某一条特定的基本路径(x, y, z)的随机游走概率分布等同于三维立方体网格中从O到顶点(x, y, z)的随机游走概率分布，这是因为：

1. 它们可能的6种移动都发生在单向量上。对于三维立方体网格来说，这是显然的。对于基本路径来说，只可能发生单向量变化或者三向量变化，如果发生了三向量变化，那么就变化成另一个基本路径了。所以对于特定的基本路径来说，只会发生单向量变化。

2. 在三个基本向量/维度上的移动可以进行交换和组合。基本路径(x, y, z)的路径长度为l = |x| + |y| + |z|，其对应的组合数为C(l, |x|)∙C(l -|x|, |y|)。

因此，对于从O到A的某个特定路径p_k = (x, y, z)，n步后质子从原点到达A的概率P(n, p_k)为

剩下的工作，就是要找出对于特定的点A，从O到A有多少条基本路径。

因为单向量变化已经被包含于基本路径之中，所以每两条基本路径之间都对应着若干次三向量变化，即

(1, ω, ω²)∙(x, y, z) = (1, ω, ω²)∙(x₀, y₀, z₀) + q(1 + ω + ω²)

对于特定的步数n和某个基本路径p_i = (x, y, z)，如果|x| + |y| + |z| > n，那么p_i对应的概率分布为0——目标明确、闷着头跑都跑不到地方。

因此，我们可以从从O到A的某一条路径(x₀, y₀, z₀)开始，先找到q_min和q_max，分别有

(1, ω, ω²)∙(x_min, y_min, z_min) = (1, ω, ω²)∙(x₀, y₀, z₀) + q_min (1 + ω + ω²)

(1, ω, ω²)∙(x_max, y_max, z_max) = (1, ω, ω²)∙(x₀, y₀, z₀) + q_max (1 + ω + ω²)

使得x_min, y_min, z_min ≤ 0，且x_min + y_min + z_min < –n；x_max, y_max, z_max ≥ 0，且x_max + y_max + z_max > n。

这样，在二维正三角形网格上用n步从O随机游走到A的概率P(n, A)就可以用以下求和表示，

最后，让我们来看看二维正六边形网格的随机游走。

在正六边形网格中，每一个顶点有3个相邻顶点。但值得注意的是，虽然组成网格的都是全等的正六边形，但顶点却有两种。以下图为例，点A为一类顶点，它的三个基本向量为-1，-ω和-ω²，而点B为另一类顶点，它的三个基本向量为1，ω和ω²。

质子在相邻的两次移动中，分别经过两类顶点各1次，所以在正六边形网格的任意一条路径中，这两类顶点交替出现。因此，如果从原点到点A的最短路径长度为n₀，那么对于任意和n₀奇偶性不同的n，P(n, A) = 0。

对于和n₀奇偶性相同的n，我们可以通过将正六边形网格转换成正三角形网格的方法求解。

假设n₀为偶数，那么只有经过偶数步后才能从原点到达A。我们把所有距离原点为偶数步的顶点用红色标记出来。可以发现，对于一个红色顶点来说，离它最近的红色顶点（相邻的红色顶点）有6个。

现在考虑质子的移动以2步为一组，那么很显然，在一组移动后质子一定会从一个红色顶点移动到相邻的一个红色顶点上，我们把这个移动用红色线段表示出来，得到了什么？

得到了一个正三角形网格！

通过简单的计算可知，在一组移动后，质子从一个红色顶点移动到一个相邻红色顶点的概率为1/3 ∙ 1/3 = 1/9，而移动一步又折返回来的概率为1/3 ∙ 1/3 ∙ 3 = 1/3。

经过转换，我们得到了一个正三角形网格，在每组移动中质子移动到相邻网格的概率为1/9，留在原网格的概率为1/3。我们可以根据以上对正三角形网络的分析得出相应的概率分布。

假设n₀为奇数，那么我们可以考虑和原点相邻的3个顶点，从这3个顶点出发经过偶数步可以到达A。所以，通过类似的方式将正六边形网格转换为正三角形网格，我们可以分别考虑从这3个顶点到达A的过程，将相应的3个概率乘以1/3再加起来即可。

2022年，有四名数学家获得了菲尔茨奖，其中法国数学家雨果·迪米尼-科潘（Hugo Duminil-Copin）的研究领域是概率论，他获奖的主要成果之一，就是自回避随机游走。自回避随机游走是一种特殊的随机游走，指的是在随机游走过程中，质子不重复进入路径中已经经过的网格顶点。

在我们的直觉中，自回避随机游走可能的路径数量要比随机游走可能的路径数量少很多。科潘证明了在二维正六边形网格中，对于长度为n的自回避随机游走路径，当n足够大时，路径的数量趋近于[√(2 + √2)]ⁿ。

对随机游走有进一步了解兴趣的读者朋友，可以参阅沃尔夫数学奖得主、芝加哥大学Gregory Francis Lawler教授所著的Random Walk: A Modern Introduction一书^【2】。

（全文完）

参考出处：

1. https://sqr5.wordpress.com/2023/07/22/%e5%96%9d%e9%86%89%e7%9a%84%e8%9c%9c%e8%9c%82%e4%b8%8e%e9%9a%8f%e6%9c%ba%e6%b8%b8%e8%b5%b0%ef%bc%88%e4%b8%ad%ef%bc%89/
2. https://www.amazon.co.uk/Random-Walk-Introduction-Cambridge-Mathematics/dp/0521519187

喝醉的蜜蜂与随机游走（中）

在本文的上篇^【1】中，我们大致了解了一维随机游走，在本文的中篇，我们继续探究二维网格随机游走。

二维随机游走指的是质子在二维平面上的随机选择移动矢量所形成的轨迹。在每一步的方向选择中，质子可以选择任意角度，每一步的步长也可以在某一个区间内随机选择，所以，一般意义上的二维随机游走大致类似于下图中的情形。

二维随机游走问题相对复杂，为了简化这个问题，我们将质子的游走限定在一个二维网格上，每一步都移动、且只移动一个单位网格的距离。严格地来说，我们在上篇中介绍的一维随机游走实际上也是一维网格随机游走，因为每一步的移动距离都被限定为一个单位整数。

最简单的二维网格即正方形网格，网格由两组平行且间距相等的网格线组成，两组网格线之间呈垂直关系，类似于我们生活中的方格纸或者坐标纸。一个二维网格随机游走过程如下图所示。

类似地，我们定义质子从坐标系原点出发，在第n步后位于坐标(x, y)的概率为P(n, x, y)。

显然，P(0, 0, 0) = 1。对于x < – n，或者x > n；或者y < – n，或者y > n，P(n, x, y) = 0。这很好理解，因为哪怕质子闷着头往一个方向移动，在n步之内它最远也只能到达(- n, 0)、(n, 0)、(0, – n)或者(0, n)。进一步推导，可以得出当|x| + |y| > n时，P(n, x, y) = 0。

与一维随机游走相比，质子在二维网格中随机游走的每一步都有4种方向选择，即x轴和y轴各自的正、负方向。

因此，如果质子在第n步到达了(x, y)，那么它必须在前一步到达与(x, y)相邻的四个网格点之一，即(x – 1, y)，(x + 1, y)，(x, y – 1)和(x, y + 1)。从四个方向移动到(x, y)的概率都为1/4，所以有以下递推公式：

P(n, x, y) = P(n – 1, x – 1, y)/4 + P(n – 1, x + 1, y)/4 + P(n – 1, x, y – 1)/4 + P(n – 1, x, y + 1)/4

现在我们有了起始条件P(0, 0, 0) = 1，有了边界条件：对于|x| + |y| > n，P(n, x, y) = 0，也有了递推公式，但以此直接推导出P(n, x, y)的解析式仍然有一定的难度。

考虑另一个办法，即利用我们在一维随机游走中得到的结论，仍然将这个二维网格随机游走问题转换成一个组合计数问题。

上图是一个n = 35，质子从原点到达点A (3, 4)的例子。在这35步中，质子在水平方向（即x轴方向）移动的步数为17，垂直方向（即y轴方向）移动的步数为18；也就是说，在水平方向，质子在17步中从坐标0移动到了坐标3；在垂直方向，质子在18步中从坐标0移动到了坐标4。

非常重要的是，在概率计算上，质子在水平方向和垂直方向的移动是相互独立的。

于是，根据在上篇中我们得出的结论，在水平（一维）方向，质子在17步后到达坐标3的概率为P(17, 3)，而在垂直（一维）方向，质子在18步后到达坐标4的概率为P(18, 4)；另外，从总共35步中选择17步水平方向（或18步垂直方向）的组合数为C(35, 17) = C(35, 18)。

因此，质子通过17步水平移动和18步垂直移动从原点到达(3, 4)的“总概率”为 C(35, 17)∙P(17, 3)∙P(18, 4)。

这是不是就是P(35, 3, 4)呢？并不是！

这是因为首先，在35步中从原点到达(3, 4)还有其它可能路径，比如在水平方向上只移动3步，直接从坐标0到坐标3，但在垂直方向上移动了32步；又比如在水平方向上移动了21步，在垂直方向上移动了14步等等。

其次，C(35, 17)是组合数，不是该组合数出现的概率，所以在将上述所有可能都计算在内的情况下，还需要除以这些组合数的总和，即ΣC(35, k) = 2³⁵。

所以，P(35, 3, 4)正确的计算公式为P(35, 3, 4) = Σ[C(35, k)∙P(k, 3)∙P(35 – k, 4)]/ 2³⁵。

一般地，P(n, x, y)的计算公式为，

将一维随机游走的概率公式代入，得到，

整理，得到，

还能再简化吗？我不知道。我只是觉得简化成这样也挺简洁的了。如果把一维随机游走的概率公式拿出来，稍作改写得到

我们就能发现这两个公式在形式上是统一的：分母分别为2ⁿ或者4ⁿ，对应于n步游走对应的所有的可能路径；分子分别是一个组合数或者类组合数。对于一维随机游走来说，这个组合数是从n中选(n + x)/2；对于二维网格随机游走来说，这个类组合数等同于从n中选k，再分别从k中选(k + x)/2和从n – k中选(n – k + y)/2等三个组合数的乘积。

根据公式形式上的相似，我们可以猜出三维网格随机游走的概率公式：对于三维立方体网格，质子从坐标系原点出发，在n步到达坐标(x, y, z)的概率为，

证明不难。在三维网格中，在每一个网格点上质子有6个等概率的移动方向，所以n步移动一共有6ⁿ种可能的路径，6ⁿ作为分母。分子对应于以下过程的组合数乘积：先从n中选i，再从i中选j，对应于在x轴方向上移动j步，y轴方向上移动i – j步，z轴方向上移动n – i步；然后从j中选(j + x)/2，从i – j中选(i – j + y)/2，从n – i中选(n – i + z)/2。

类似地，大家可以得到更高维空间网格随机游走的概率公式，这里不再赘述。

对于有边界的二维网格随机游走，其基本思路虽然和一维随机游走类似，比如只有质子在边界上时，方向的选择在某一维上才不是等概率的，才会对位置的数学期望有贡献。但是，我们不能简单地认为，有边界条件下边界内的点的概率与无边界条件下相应的概率存在倍数关系，这是因为边界的“镜面对称”只对二维中的某一维有效。

这个不同使得对带边界的二维随机游走问题中概率的计算变得复杂了很多。

以质子位于坐标(0, 3)时为例。在无边界条件下，下一步质子可能到达(-1, 3)、(1, 3)、(0, 2)和(0, 4)四个点之一，到达每一个点的概率都是1/4；现在我们把y轴当作边界，只允许质子在+x的半个平面移动，那么在下一步，质子只有可能到达(1, 3)、(0, 2)和(0, 4)三个点之一，到达每一个点的概率变成了1/3。注意，水平方向移动到(1, 3)的概率从1/4变成了1/3，并没有变成原来的2倍；而垂直方向移动到(0, 2)或者(0, 4)的概率同样从1/4变成了1/3，而不是与原来保持不变。

在y轴作为边界、只允许质子在+x的半个平面移动的情况下，显然质子在(+x, +y)和(+x, –y)两个象限里的概率分布是对称的，所以我们可以考虑将质子在二维平面上的移动投影到x轴上，从而把这个二维问题简化成一维问题。

和一般性的一维随机游走不同的是，投影后质子在x轴上的移动并不是简单地等概率向左或者向右，而是存在一定的概率在水平方向上保持不变——其对应的是质子在二维平面上向上或者向下的移动。

在上图中，如果质子位于y轴上，那么它有相同的1/3的概率向右、向上或者向右移动，投影到x轴上后，等同于质子有1/3的概率向右移动，另有2/3的概率选择不动。如果质子不在y轴上，那么它有相同的1/4的概率向左、向右、向上或者向下移动，投影到x轴上后，等同于质子有相同的1/4的概率向左或者向右移动，另有1/2的概率选择不动。

看到这张图，读者朋友们一定可以回想起我们曾经介绍过的马尔可夫链^【2】。事实上，随机游走问题尤其是一维随机游走问题可以很好地用马尔可夫链来表示，而赌徒输光定律本质上就是一个一维随机游走问题。

我们将投影后质子在x轴上移动的概率用下面的马尔可夫链表示。

用P(n, x)表示从原点出发n步后，质子出现在坐标x处的概率——实际上等同于投影前，从原点出发n步后，质子的横坐标等于x的概率。

显然，初始条件为：P(0, 0) = 1，对于正整数x，P(x, 0) = 0。

马尔可夫链对应的三个递推公式为：

P(n, 0) = P(n – 1, 0)∙2/3 + P(n – 1, 1)∙1/4

P(n, 1) = P(n – 1, 0)/3 + P(n – 1, 1)/2 + P(n – 1, 2)/4

P(n, x) = P(n – 1, x – 1)/4 + P(n – 1, x)/2 + P(n – 1, x + 1)/4，x > 1

如果用一个矩阵来表示从第n – 1步到第n步概率的转换，我们可以得到如下概率转换矩阵T：

而概率分布的初始状态也可以用一个行向量p₀ = (1, 0, 0, 0, 0, …)表示。那么n步后的概率分布p_n可以通过将p₀与转换矩阵T连续相乘n次而获得：

这样，我们只需先计算出T的n次幂，然后取出结果的第一行（即将p₀与结果相乘），就得到质子在每一个整数横坐标上的概率分布向量了，P(n, x)即向量p_n的第x个元素。

可能有读者会问，T是一个无限矩阵，如何计算它的幂？

在实际计算中，我们可以利用另外一个隐含条件：即n步后，质子在水平方向可能到达的最远距离为n（闷着头一个劲儿地向右跑）。这样，我们可以截去矩阵T中行和列下标大于n的部分，只需计算n × n方阵的n次幂即可。

通过以上方法，我们可以得到质子位置横坐标的概率分布。同样，如果将质子在二维平面上的移动投影在y轴上，那么类似地我们可以将这个问题简化成一个在y轴上的一维问题，利用马尔可夫链或者概率转换矩阵，可以求得n步后质子位置纵坐标的概率分布。

两者结合起来，我们就得到了有边界条件下的二维随机游走的概率分布。

至此，我们大致了解了二维随机游走，在本文的后续部分，我们将进一步了解在其它类型的网格中的随机游走模型，了解“花蜜蜂”在闯入蜂巢以后，它将如何在正六边形网格上进行随机游走。

（未完待续）

参考出处：

1. https://sqr5.wordpress.com/2023/07/20/%e5%96%9d%e9%86%89%e7%9a%84%e8%9c%9c%e8%9c%82%e4%b8%8e%e9%9a%8f%e6%9c%ba%e6%b8%b8%e8%b5%b0%ef%bc%88%e4%b8%8a%ef%bc%89/
2. https://sqr5.wordpress.com/2023/07/01/%E8%B5%8C%E5%BE%92%E8%BE%93%E5%85%89%E5%AE%9A%E5%BE%8B%E8%83%8C%E5%90%8E%E7%9A%84%E9%A9%AC%E5%B0%94%E5%8F%AF%E5%A4%AB%E9%93%BE/

喝醉的蜜蜂与随机游走（上）

今年，太平洋热带海域七年以来又一次形成厄尔尼诺现象，与之伴随而来的是全球多地出现酷暑高温天气以及洪涝灾害。在疫情防控放开后的第一个暑假，不少朋友带着孩子回国探亲和旅游，纷纷表示国内天气太热，孩子差点儿被热化了。

酷暑和暴雨不仅给人类的生活带来了不便和挑战，而且会加速野外花蜜的自然发酵过程，使得花蜜中的糖分发酵成为酒精。研究表明^【1】，如果蜜蜂在采蜜过程中摄入了过多的天然酒精，那么它们也会表现出醉酒的行为：飞行姿态变得跌跌撞撞，忘记回到蜂巢的路线，甚至有可能跌落地面而发生猝死。

有意思的是，守卫蜂巢的工蜂在看到喝醉了的蜜蜂返巢时，会拒绝它们进入，以免蜂巢内的蜂蜜被带入的酒精所污染。我在想：如果有一只又大又壮的蜜蜂喝醉了，会不会也上演一出“醉打山门”，最终闯入蜂巢？

现在，我们将这只醉酒闯入蜂巢的“花蜜蜂”看作位于平面上一个无限大正六边形网格上的一个点，在每一个网格节点上，它将在3个相互夹角均为120°的方向中随机选择1个，来到下一个网格节点，我们将这个过程称为蜜蜂随机游走了1步。

上图中，蜜蜂从O点出发，随机游走了8步，以蓝色实线箭头表示。每一步蜜蜂都有3个方向进行随机选择，以红色虚线箭头表示。

问题来了：如果蜜蜂从O点出发，在随机游走n步之后，它到达另一个点P的概率是多少？

这一类问题被称为“随机游走问题”（RW，Random Walk），1905年由英国数学家卡尔·皮尔逊（对，就是Pearson相关系数的那个Pearson）首次提出。随机游走由一连串的运动轨迹组成，其中每两步之间都是一个随机过程。随机游走广泛地应用于诸多科学和技术领域，比如它可以用来模拟物理学中的布朗运动和生态学中的生物扩散以及种群动态，也可以用来模拟股票价格波动和社交媒体网络中的好友推荐等等。

按照惯例，我们从最简单的一维随机游走模型开始。

一维随机游走模型可以看作一个质点从数轴的原点出发，每一步随机选择沿数轴正向或者负向移动1个整数单位。我们用t表示步数变量，x表示质点所在的位置，n表示总步数，P(n, x)表示n步后质点位于x处的概率。

根据这个模型，质点要在第n步后到达x，那么它必须在第n – 1步时位于x – 1或者x + 1。这样，我们可以得到递推公式：

P(n, x) = P(n – 1, x – 1)/2 + P(n – 1, x + 1)/2

有那么一点点像斐波那契数列？为了得到更直观的结果，我们可以模拟计算一下最开始的几步。

当t = 0时，显然由P(0, 0) = 1。对于其它的x ≠ 0，P(0, x) = 0。

当t = 1时，质点到达-1或者1，概率各为1/2，所以

P(1, -1) = P(1, 1) = 1/2。

对于-1和1以外的x，P(1, x) = 0。

当t = 2时，如果前一步质点在-1，那么这一步它到达-2或者0；如果前一步质点在1，那么这一步它到达0或者2，四个事件发生的概率各为1/4。所以

P(2, -2) = P(2, 2) = 1/4，P(2, 0) = 1/4 + 1/4 = 2/4。

对于-2、0和2以外的x，P(2, x) = 0。

类似地，当t = 3时，有

P(3, -3) = P(3, 3) = 1/8，P(3, -1) = P(3, 1) = 1/8 + 1/4 = 3/8。

对于-3、-1、1和3以外的x，P(3, x) = 0。

……

上图很直观地表示了P(n, x)取值的规律：它和杨辉三角形非常相似，只不过同一层每两个位置之间相差为2，每两层分母之间公比为2。

受到P(n, x)和组合数关系密切的启发，我们可以把一维随机游走的过程看成一个n中选k的过程，即质点从原点出发后的n步中有k步向数轴正方向，其余n – k步向数轴负方向，这样，质点最后的位置为x = k – (n – k) = 2k – n，即k = (n + x)/2。

注意到k为正整数，所以n和x奇偶性必须相同。

在一维随机游走中，n步可能的过程一共有2ⁿ种，n中选k的组合数为C(n, k)。

我们定义：k < –n，或者k > n，或者k为非整数时，C(n, k) = 0。这样，

P(n, x) = C(n, k)/2ⁿ = C(n, (n + x)/2)/2ⁿ。整理后得到：

相应地，定义负数及非整数的阶乘为无穷大即可。

在一维随机游走中，有一类稍微特殊些的问题，问题中设有一个或者两个边界，规定质子无法越过边界。比如，假设酒馆位于数轴原点，一个酒鬼从酒馆出来，他的家在数轴+100的位置，酒鬼每次从酒馆出发时，酒保都会引导他朝家的方向走。这样，在原点处质子的方向始终只能选择进入数轴正半轴，这也意味着质子无法进入数轴的负半轴。

问题来了：在边界设在原点的一维随机游走问题中，n步随机游走后，质子位置的数学期望值是多少？

从上图中可以看出，带边界的一维游走和不带边界的一维游走略有不同：

对于原点来说，其概率值没有差别；对于正半轴上的点来说，其概率值等于不带边界的一维游走问题中相应概率值的两倍——这很好理解，因为设立在原点处的边界类似于一个镜面，将本来在全数轴上呈对称分布的概率值折合叠加在正半轴上，所以正半轴上所有的概率值都变成了原来值的2倍。

因此在这个带边界的问题中，对于正整数n和x，

同样，负数及非整数的阶乘被定义为无穷大。

现在来计算n步随机游走后质子位置的数学期望值。因为当x = 0时，对位置数学期望的贡献为0，且当x > n时，P(n, x) = 0。所以求和中x的区间可以缩小为[1, n]：

等式右侧的求和，可以通过换元以后再利用恒等式

证明方法可以参见我们昨天的文章^【2】。

也可以使用裂项法，我们观察到(n + x)/2 – (n – x)/2 = x，所以

当n为偶数时，所有奇数x项等于0，x从2开始求和直到n，裂项简化后

当n为奇数时，所有偶数x项等于0，x从1开始求和直到n，裂项简化后

我们可以利用向下求整符号将两个公式统一起来：

令m = 2⌊n/2⌋，则在边界设为0的情况下，n步随机游走后质子位置的数学期望值为

可以注意到，对于一组连续的奇数和偶数，其E(n)相等，比如E(1) = E(2)，E(3) = E(4)，E(5) = E(6)等等。

要理解这个，可以回过头来考虑无边界的一维随机游走，因为其概率分布关于原点对称，所以对于无边界的一维随机游走，E(n)恒等于0。

就好比在一根细长的、装满清水且水平放置的试管中部（原点）滴一滴墨水，墨水将对称地向试管两端扩散，不论扩散到什么程度，墨水的质心仍然在原点，即数学期望值为0。

如果在原点处插入一个隔板，墨水滴在隔板的右侧，那么随着墨水在清水中的扩散，其质心逐渐向右移动。墨水整体移动的“动力”，来自于隔板对那些向左运动的墨水颗粒的反向作用力。

回到我们的模型。

从t = 0到t = 1的过程中，原点处的质子只有一个方向，即向右移动到1处。此时，质子的运动并不是随机的，而是必然的。

从t = 1到t = 2的过程中，质子不可能位于原点，因此此时质子的移动是随机的；换句话说，就是位置的数学期望值保持不变，即E(1) = E(2)。

从t = 2到t = 3的过程中，质子有1/2的概率位于原点。类似地，位于原点的质子获得了隔板的反作用力，它必然向右移动到位置1。尽管此时质子也有1/2的概率位于位置2，从位置2出发的游走是完全随机的，但综合起来，质子仍然有1/2的概率获得确定性的、向右的移动。

这样，在t从奇数变为偶数的过程中，质子不可能出现在原点，所以游走是完全随机的，其位置的数学期望值保持不变；而在t从偶数变为奇数的过程中，质子有一定概率出现在原点，从原点出发必然向右移动到位置1，所以游走并不是完全随机的，其位置的数学期望值得到了增加。

这样，E(n)在一组连续的奇数和偶数上保持相等，就不难理解了。

最后，我们来估计一下E(n)的增长速度。

将E(n)重新写成阶乘的形式：

根据斯特林公式（Stirling’s formula），对于足够大的整数n，

同样对于足够大的整数n，n ≈ m。不妨令n ≈ m = 2k，同时将斯特林公式代入，得到

因此，当n足够大的时候，E(n)与√n的增长速度处于同一水平。

举例来说，如果酒鬼的家位于离酒馆100步的位置上，没喝酒时他只需要走100步便能回家；而喝醉了以后，他成为了一个在带边界的一维空间中随机游走的质子，按照上面的估算，他平均需要走5000π ≈ 15708步才能到家。

至此，我们大致了解了一维随机游走，在本文后续部分，我们将进一步了解二维网格随机游走。

（未完待续）

参考出处：

1. Abramson CI, et al. The development of an ethanol model using social insects I: Behavior studies of the honeybee (Apis mellifera L.) Alcohol Clin Exp Res. 2000;24:1153–1166. doi: 10.1111/j.1530-0277.2000.tb02078.x.
2. https://sqr5.wordpress.com/2023/07/19/%e7%8e%bb%e7%92%83%e6%a1%a5%e4%b8%8a%e5%87%a0%e4%ba%ba%e8%bf%98-%e3%80%8a%e9%b1%bf%e9%b1%bc%e6%b8%b8%e6%88%8f%e3%80%8b%e4%b8%ad%e7%9a%84%e6%a6%82%e7%8e%87%e9%97%ae%e9%a2%98/

玻璃桥上几人还——《鱿鱼游戏》中的概率问题

高空玻璃桥是《鱿鱼游戏》中的第五个游戏，游戏的设定是这样的：

在高空上建有一座玻璃桥，桥面一共由18步组成，每一步有左右两块玻璃可供选择，其中一块玻璃为普通玻璃，无法承受游戏者的体重；另一块为强化玻璃，游戏者可以在上面安全跳跃或者站立。

因为两块玻璃在外观上别无二致，所以对于排在队列首位的游戏者而言，每一步都有50%的概率选中普通玻璃，从高空坠落；也有50%的概率选中强化玻璃，从而可以继续下一步的选择。而排在队列后面的游戏者可以跟随前面的游戏者一直走在安全的玻璃上，直至前面的游戏者一一被淘汰、自己变成队列中的首位，从而不得不进行选择。

在韩剧《鱿鱼游戏中》，16名游戏者组成一个队列挑战高空玻璃桥，最终只有3人幸存。因为剧情需要，这个过程中有好几名游戏者因为内斗而从高空中坠落，也有游戏者通过观察两种玻璃之间的细微差别而做出过正确的选择，所以3人幸存的结果并不符合游戏设定本身所带来的幸存概率。

那么抛去剧情，纯粹从游戏设定出发，16名游戏者挑战由18步组成的玻璃桥，最后期望的幸存者有几名？

游戏者在每一步的选择中，成功和失败的概率各半，类似于抛硬币。所以粗略来说，走一步，游戏者平均要丢半条命；走两步，游戏者平均要丢一条命——换句话说，一名游戏者平均走两步后就会被淘汰。

更为严格一些来说，假设每个游戏者的期望步数为E_L，走1步后被淘汰的概率为1/2，走2步后被淘汰的概率为1/4，走3步后被淘汰的概率为1/8……，走k步后被淘汰的概率P_k为1/2^k，所以有：

E_L = ∑(P_k∙k) = ∑(k/2^k)

为了求这个无穷级数，可以将等式两边乘以2：

2E_L = ∑(k/2^k-1)

再减去前面的等式，得到：

E_L = 2E_L – E_L = ∑(k/2^k-1) – ∑(k/2^k)

利用错项法，可以得到：

E_L = 1 + ∑(1/2^k) = 2

这个结果说明，要走完18步，需要“牺牲”9名游戏者，所以对于16名游戏者组成的队列，最后幸存人数将为7名。

那么，幸存人数的数学期望真的等于7吗？进一步的计算可以发现，这个数值将稍稍大于7，大约为7.0000763。

让我们把游戏规则背后的数学重新捋一遍。

游戏者每一步的选择对于游戏者本身来说，其结果要么被淘汰，要么安全进入下一步；从另一个角度来看，不论这名游戏者被淘汰还是进入下一步，对于后续的游戏者而言，通过这一选择，这一步中哪一块玻璃是安全的从此成为已知的信息。

游戏由18步组成，从以上角度上来看，要试出每一步的安全信息，需要且只需要游戏者做出一次选择。对于所有的18步，需要且只需要18次选择。在最差的情况下，这18次选择由18名不同的游戏者做出，且每个人的运气都不好，即有18名游戏者被淘汰；而在最好的情况下，这18次选择由同1名游戏者做出，且每一次选择的运气都很好，即无1游戏者被淘汰。

因此，我们可以用一个18位的二进制数来表示这一个游戏过程：从高位到低位，每一个数位对应游戏中从1到18的某一步，0表示安全，1表示被淘汰。

例如：110000110010010101表示有8名游戏者被淘汰，分别在游戏中的第1、2、7、8、11、14、16和18步没有做对选择。

又如：000000001000000000则表示只有第1名游戏者被淘汰，他在前8次选择中都做对了选择，第9次选择失败被淘汰；第2名游戏者在后面的9步中一路开挂，成功过关。

18个数位的二进制数对应着2¹⁸种可能，所以，

全员16人幸存（或无人被淘汰）的概率为C(18, 0)/ 2¹⁸（即18个数位中有0个数位为1）；

幸存15人（或1人被淘汰）的概率为C(18, 1)/ 2¹⁸（即18个数位中有1个数位为1）；

幸存14人（或2人被淘汰）的概率为C(18, 2)/ 2¹⁸（即18个数位中有2个数位为1）……

幸存16 – k人（或k人被淘汰）的概率为C(18, k)/ 2^k（即18个数位中有k个数位为1）。

注意，对于16名游戏者参加的游戏，k的最大值为16，即最多有16名游戏者被淘汰。

这样，如果用k代表被淘汰的游戏者人数，这个游戏中幸存人数的数学期望E_S为：

其中，

所以，

即，幸存人数略大于7人，其小数部分为5/2¹⁶，恰好是求和中补足的最后两项。

如果正好有18名游戏者参加游戏，游戏者人数和游戏步数相等，那么在上述推导中无需进行补足，E_S将正好等于18 – 9 = 9。

反之，如果只有14名游戏者参加游戏，那么在上述推导中需要补足求和中的最后四项，这四项之和要大于5/2¹⁶，最后得到的E_S大约为5.0045。

而如果正好有9名游戏者参加游戏，幸存者期望人数并不是我们直观感觉中的0，而是大约为0.8346，即有相当的可能第9人闯关成功。

赌徒输光定律背后的马尔可夫链

昨天在某论坛上看到一道高中概率题。题目的表述是这样的：

在某中学体育课的投篮测试中，测试者连续进行定点投篮，直到出现下面两种情况之一时结束：如果出现连续三次投篮都命中，则标记为测试通过；如果出现连续两次投篮都没有命中，则标记为测试失败。如果某测试者每次投篮命中的概率都为2/3，求其通过该测试的概率。

这是一道规则清晰的概率题，连续三次命中即通过，连续两次没命中则失败。

比较绕的地方在于测试者投篮的次数并不固定，最少可能两次、三次便以失败或者成功结束，如果命中和没命中交替出现的话，测试者将一直投下去。

比较简单的地方在于每一次投篮的命中率是固定的，并不会受到当前所处状态的影响。

对于这种状态之间转移多变、但概率相对固定的题目，我们可以利用一个很好的工具，那就是马尔可夫链。

马尔可夫链因俄罗斯数学家安德烈·马尔可夫（Andrey Markov）得名，它以直线链或者图论的方式描述随机过程中从一个状态到另一个状态的转换概率。在马尔可夫链中，从某一个状态转换到下一个状态的概率只由当前状态有关，而和链上当前状态之前的状态无关。

马尔可夫链广泛地应用于物理、化学、 语音识别 、信息科学、金融等领域。在人工智能和深度学习应用遍地开花的今天，对未来天气的准确预报仍然是一个尚未解决的问题，这是因为影响天气的大气因素非常多，甚至亚马逊雨林中一只蝴蝶扇动翅膀都有可能给得克萨斯州带来一场龙卷风（蝴蝶效应）。在这里，我们用天气预报作为一个不够准确的例子，简单地说明一下什么是马尔可夫链，以及马尔可夫链在随机过程中概率计算的应用。

在这个极简的模型中，每天只有两种天气状态，要么是晴天，要么是雨天。下一天的天气状态只取决于当天的天气状态，而与之前的天气状态无关，所以我们可以把若干天的两种天气状态表示为一个链状的形式：

假设从某一天的天气状态到下一天的天气状态的转换概率可以用一个2×2的表格来表示：

	下一天晴天	下一天雨天
当天晴天	0.8	0.2
当天雨天	0.4	0.6

具体来说，如果今天是晴天，那么明天继续晴天的概率是0.8，出现雨天的概率是0.2；如果今天是雨天，那么明天继续下雨的概率是0.6，雨过天晴的概率是0.4。那么我们的天气状态转换链就加上了每一对状态之间转换的概率：

在数学中，这个2×2的表格可以表述为一个二阶的矩阵，即状态转换矩阵，或者状态转换概率矩阵。我们可以通过将当前天气的状态向量乘以状态转换矩阵，得出下一天的天气状态向量；进一步，在理想的情况下，还可以一直通过这种矩阵相乘，得出以后任意一天的天气状态向量。

比如，今天是晴天，天气状态向量为(1 0)，我们通过将这个向量和状态转换矩阵连乘三次得出对三天后天气状态的一个估计：

可以看出，三天后仍然是晴天的概率大约为2/3（86/125），三天后是雨天的概率大约为1/3（39/125）。

当然，现实中的天气预报并没有这么简单。

现在我们回到投篮测试的问题。

和天气预报不同，测试是否通过不是取决于某一次投篮是否命中，而是取决于是否出现连续命中或者连续没命中。因此，这个问题中的状态就不再是“命中”或者“没命中”，而应该是“连续x次命中”或者“连续x次没命中”。

按照这个思路，我们构建投篮测试问题的马尔可夫链：

在这个马尔可夫链中，有一个明确的起点状态、两个可能的终点状态，以及三个可能的中间状态。每一对相邻状态之间的转换概率由题目条件所给出：单次投篮命中概率为2/3，没命中的概率为1/3。

现在，我们需要求出从“开始测试”起点状态转移到“连续3次命中”终点状态的概率。

不妨设从“开始测试”，“1次没命中”，“1次命中”，“连续2次命中”转移到“连续3次命中”的概率分别为P₀，P_-1，P₁，P₂。

因为第一次投篮的结果只可能是“命中”或者“没命中”，所以从“开始测试”转移到“连续3次命中”的过程必然要经过“1次命中”或者“1次没命中”，考虑到投篮命中的概率，可以得到如下方程：

P₀ = 1/3∙P_-1 + 2/3∙P₁

类似地，对每一个中间状态都做如上分析，得到方程组：

P₀ = 1/3∙P_-1 + 2/3∙P₁
P_-1 = 1/3∙0 + 2/3∙P₁
P₁ = 1/3∙P_-1 + 2/3∙P₂
P₂ = 1/3∙P_-1 + 2/3∙1

在第2个方程中的0对应于“连续2次没命中”的终止状态，测试以失败结束，从这个状态转移到“连续3次命中”状态的概率为0。在第4个方程中的1对应于“连续3次命中”的终止状态，测试以成功结束，所以从这个状态转移到自己的概率为1。

解以上线性方程组，可以得到

P₀ = 32/51
P_-1 = 8/17
P₁ = 12/17
P₂ = 42/51

即在投篮测试开始时，最后通过测试的概率为32/51。

下面，我们来简化一个赌博游戏。

假设赌徒带了5元赌本，每次下注固定为1元，每次下注的输赢由扔硬币决定，即输和赢的概率都为1/2，输了损失1元，赢了赚取1元。

因为每次下注的输赢概率相等，所以很显然，如果赌徒的目标是赌本翻倍，即赢取5元，那么这个概率和他输光赌本5元的概率是相同的。

如果赌徒贪得无厌，他把目标定在赢取10元，或者赢取15元，对应的成功的概率分别是多少呢？

我们把赌徒手中赌金可能的数额作为这个过程中的状态，以赢取10元为例构建马尔可夫链：

因为每注输赢的概率都为1/2，所以上图中所有箭头上的概率都是1/2。

类似地，假设从赌金为1，2，3，…，14元的状态转移到赌金为15元（即赢取10元）的状态的概率分别为P₁，P₂，P₃，…，P₁₄。

列出线性方程组：

P₁ = P₂/2 + 0/2
P₂ = P₃/2 + P₁/2
P₃ = P₄/2 + P₂/2
…
P₁₃ = P₁₄/2 + P₁₂/2
P₁₄ = 1/2 + P₁₃/2

或者：

P₀ = 0, P₁₅ = 1, 对于1 ≤ k ≤ 14：P_k = P_k+1/2 + P_k-1/2。

通过求不动点的方法^【1】，可以得到通项公式：P_k = k/15。因为赌徒的本金为5元，所以只需考察P₅ = 5/15 = 1/3。

一般地，对于赌本m元，赢取n元目标实现的概率为，P_{m, n} = m/(m + n)。

这样对于有着5元赌本的赌徒来说，实现赢取10元这个目标的概率为P_{5, 10} = 1/3，实现赢取15元这个目标的概率为P_{5, 15} = 1/4。

赌徒越贪心，实现其贪心目标的概率越小，这是显见的。

有一个著名的定律，叫做“赌徒输光定律”。这个定律的意思是，一个有着赌本为n的赌徒去赌博，如果他贪婪成性，一直赌下去，那么总会在有限轮次后输光自己全部的赌本。

对这个定律的证明，即可以利用刚才我们通过马尔可夫链得出的结论。

假设赌徒和庄家对赌，赌徒的赌本为n，庄家的赌本为10n。在双方都不出老千的情况下，即每注的输赢概率都在1/2，双方一直赌下去，直到一方赌本归0，另一方赢者全得。

根据上述我们得到的结论，赌徒赌本为n，目标是赢取10n，其成为最后赢家的概率为P_{n, 10n} = 1/11；庄家赌本为10n，目标是赢取n，其成为最后赢家的概率为P_{10n, n} = 10/11。由此可见庄家获胜的概率是赌徒获胜概率的10倍。

现实中，庄家的赌本要远远大于赌徒的赌本，所以只要赌徒一直赌下去，庄家赢光赌徒赌本的概率就非常非常大；换句话说，赌徒在有限轮次后输光自己赌本的概率也非常非常大。

参考出处：

1. https://sqr5.wordpress.com/2020/01/22/%e4%b9%94%e4%bc%8a%e7%9a%84%e5%9c%b0%e5%9b%be/

浪漫的三十人聚会

经济学家劳拉∙费维森（Laura Feiveson）先后毕业于耶鲁大学和麻省理工大学，现任职于美国财政部。

费维森曾经讲述过一个家庭中流传的故事。

那是在很多年前的一个聚会上，费维森的父亲第一次遇到她的母亲，就深深地被其魅力所吸引。参加聚会的朋友有30人左右，费维森的父亲对心仪的姑娘说：“我打赌，这30人中一定有两个人生日相同。”

姑娘并不相信在这个小型聚会上出现两个人生日相同的概率会这么高，她觉得这只不过是男孩子搭讪女孩子的套话罢了。

“我们不妨试试，你的生日是什么时候？”小伙子并没有放弃。

“5月20日。”姑娘回答说。

“我也是5月20日！”小伙子激动地回应着。

从此，两个人迅速地步入了恋爱和婚姻之中。

这个故事里有没有演绎的成分不好说，尤其是第一次见面的男女主角恰恰就在同一天生日，这CP也太好嗑太美好了吧！

不过，任意找出30人，就有两人的生日相同的概率究竟有多大？费维森父亲的打赌到底是搭讪的套话，还是面对心仪姑娘抛出的求爱陷阱？

这些问题可以通过数学来回答。

学过抽屉原理的朋友对下面这个论断一定不会感到陌生：

任意找出367个人，其中至少有2人生日相同。

加上闰年的2月29日，可能的生日一共只有366天，当人数大于366时，必然至少有2人的生日落入同一天。这个是不需要概率计算就可以得出的结论。

不过，当聚会的人数只有30人时，两人生日相同的事件并不是必然发生的。这里我们需要用概率计算来得出费维森父亲胜算的大小。

我们考虑这个事件的补集，即：在n个人参加的聚会上，没有两个人生日相同。

先考虑第1个人，他的生日可以是366天中的任意一天。同时也肯定没有人和他生日相同，所以概率为1。

再考虑第2个人，他的生日要避开第1个人的生日，只有365个选择。所以这2人生日不同的概率为1∙365/366。

然后考虑第3个人，他的生日要避开前2人，因此只有364个选择。3个人生日互不相同的概率为1∙365/366∙364/366。

依此类推，第n个人的生日只有367 – n个选择。所有n个人生日互不相同的概率为：

那么，“在n个人参加的聚会上，至少有两个人生日相同”事件发生的概率即：

我们代入几个不同的聚会人数，来体会一下这个概率究竟有多大。

当n = 5时，P₅ = 2.7%，出现两人同一天生日的概率比较小。

当n = 10时，P₁₀ = 11.7%，出现两人同一天生日的概率超过10%了。

当n = 23时，P₂₃ = 50.6%，出现两人同一天生日的概率已经超过了一半。

当n = 30时，P₃₀ = 70.5%，费维森老爷子一定是经过深思熟虑的！

当n = 40时，P₄₀ = 89.1%，概率已经接近90%了。

当n = 50时，P₅₀ = 97.0%，如果聚会上有50人，那么出现两个人生日相同几乎是必然了。

抽屉原则中剩下的那310多人的贡献仅仅将概率从97%提高到100%。

注意：以上推导中其实还有一个小小的偏差，即366个生日在人群中并不是等概率的分布，2月29日生日的人要比其它日子生日的人少3/4左右，所以对于任意n个人参加的聚会，出现两人同生日事件的实际概率要比上面的结果略微高一点点。

该吃哪种药呢？

首先申明，这只是一道虚构的数学题，没有别的意思。

假设在某种病毒引起的大流行中，被感染者中有一半的人最后会留下严重的后遗症甚至失去生命，另一半人则可以自愈。现在市面上出现了两种药物，但都还没有经过严格、广泛的测试，其中药物A曾用于3名患者，最后3名患者都痊愈了；而药物B曾用于8名患者，最后8名患者中有7名痊愈，1名留下了严重的后遗症。

如果很不幸，你发现自己感染了这种病毒，但万幸的是，你的朋友可以给你提供A、B这两种药物，你应该选择使用哪种药物？

有读者可能会说，药物A好，因为虽然参与测试的患者不多，但毕竟有效率100%；也有读者可能会说，药物B好，虽然有1例效果不理想，但参与测试的患者多，得到的结果也更可信。

下面，我们从纯数学的角度帮你分析一下，应该选择哪种药物。

首先，如果不吃药，会发生什么？这个概率相当于抛硬币：一半的人要糟糕，另一半人则会自愈。所以哪怕不吃药，你痊愈的可能性也有1/2。

然后，我们考虑3名感染者。如果服用药物A，根据测试结果，这3名感染者都会痊愈。那么如果不吃药，3名感染者最后都自愈的概率是多大呢？根据上面的“抛硬币”，他们全部自愈的概率是1/2∙1/2∙1/2 = 1/8。换句话说，服药后100%有效，但即便不服药，达到全部自愈的概率也有1/8。

我们再考虑8名感染者。如果服用药物B，根据测试结果，其中1人效果不佳，另外7人将会痊愈。不吃药的话，8人中有7人自愈的概率有多大呢？同样根据上面的“抛硬币”，他们中有7人自愈的概率为8∙(1/2)⁸ = 1/32。也就是说，服药后7/8的人痊愈，如果不服药，同样是7/8的人自愈的概率只有1/32。

因此，对于同样的结果——3人痊愈，或者8人中有7人痊愈，服用药物A可以把概率从1/8提升到100%，服用药物B则可以把概率从1/32提升到100%。可见药物B要比药物A更有效。

当然，以上只是纯数学范畴的概率计算。如果真在现实生活中碰到这种情况，我建议大家两种药都不要吃，因为参与这两种药物临床测试的人数都太少了，数据可靠性不高，药物有效性和安全性都得不到保证。

即便不吃药，至少咱还有抛硬币的机会嘛。

《决赛前的期望》补充

前文《决赛前的期望》^【1】发布之后，有朋友问4组各4支球队的排列数计算是否有更简便一些的办法，答案是肯定的。

前文中采用的是“插位法”，即先固定4支出线队伍A、B、C和D的位置，然后将它们小组赛的对手逐一插入到排列中，因为小组赛对手排名都不如这4支队伍高，所以它们被相应地插入到4支队伍的右边。

“插位法”的优点是直观，缺点是有些繁琐。

解决这个问题有另一种思路，就是先不管三七二十一，在没有任何条件的情况下混排所有16支队伍，然后再根据条件剔除不符合题意的排列。

情况1：ABCD。

16支球队的全排列一共有16!种可能。

考虑16支球队的全排列中每个小组4支球队的排列，比如A，a₁，a₂和a₃，在这4支球队的排列中A的相对位置有4种，即A分别排在4支球队的第1位，第2位，第3位和第4位，其中只有A排在第1位符合题意（A从这个小组出线）。所以16支球队的全排列中只有1/4的排列符合A从小组出线这个条件。

同样考虑球队B、C和D所在小组的情况，这样我们得出，16支球队的全排列中只有1/4⁴的排列符合A、B、C和D分别从各自小组出线的条件。

再考虑4支出线球队之间的排列，如果无任何限制条件，A、B、C和D的全排列有4!种，但根据题意，情况1只有ABCD这1种固定排列，所以16支球队的全排列中只有1/4!的排列符合4支球队以ABCD这个顺序排列的条件。

综上，符合情况1的排列总数为16!/(4⁴∙4!)，这个结果和前文中得到的15!/(4∙8∙12)是相同的。

情况2：ACBD。

如同前文中所指出，出于球队B和C的对称性，情况2和情况1的排列数是相同的。

我们也可以从16支球队全排列出发，得出情况1和情况2综合在一起的排列数。如果不考虑B和C谁在左边谁在后边，那么在考虑出线4支球队排列时，只需要考虑A{BC}D这种情况，其中{BC}表示B和C两支球队相邻。这样，4支出线球队的排列就不是4!了，而是3!∙2，其中3!是A、{BC}和D 三个元素的全排列，2是B和C之间互换的排列顺序。

易知，16!/(4⁴∙3!∙2) =  16!/(4⁴∙4!) + 16!/(4⁴∙4!)。

情况3.1：A排名第2，c₁，c₂和c₃都在A的右边。

这种情况下，C和A被固定在第1位和第2位，其它14支球队排在A的右边。

14支球队的全排列为14!，考虑球队B和D必须从所在小组出线，符合这两个条件的排列数为14!/(4²)。然后考虑14支球队中B必须排在D的左边，所以再除以2，得出情况3.1的排列数为14!/(4²∙2)，这个结果和前文中得到的14!/(4∙8)是相同的。

情况3.2：A排名第3，c₁，c₂和c₃中有1支球队在A的左边，其他2支在A的右边。

类似于前文，先3选1，P(3, 1) = 3，选出一支c_x放排在A的左边，这样Cc_xA固定在前3名。其它13支球队排在A的右边。

类似于情况3.1，13支球队的全排列为13!，考虑球队B和D必须从所在小组出线、且考虑13支球队中B必须排在D的左边，得出情况3.2的排列数为3∙13!/(4²∙2)，这个结果和前文中得到的3∙13!/(4∙8)是相同的。

情况3.3：A排名第4，c₁，c₂和c₃中有2支球队在A的左边，另外1支在A的右边。

先从3支c球队中排列出2支c_x和c_y，放在A的左边，即有P(3, 2) = 6种可能。固定Cc_xc_yA在前4位，其它12支球队排在A的右边。

类似地，在12支球队的全排列中考虑球队B和D必须从所在小组出线、且考虑12支球队中B必须排在D的左边，得出情况3.3的排列数为6∙12!/(4²∙2)，这个结果和前文中得到的6∙12!/(4∙8)是相同的。

情况3.4：A排名第5，c₁，c₂和c₃都在A的左边。

对3支c球队进行全排列，共P(3, 3) = 6种可能。固定Cc_xc_yc_zA在前5位，在剩下11支球队的全排列中考虑B和D的出线、且B排在D的左边，因此得出情况3.4的排列数为6∙11!/(4²∙2)，这个结果和前文中得到的6∙11!/(4∙8)是相同的。

根据这个思路，我们可以将这个问题一般化，对于以下情况：

4m支球队被随机分为4组，每组m支球队，其中排名最高的球队进入半决赛。在半决赛中，球队A淘汰了球队B，球队C淘汰了球队D，且在三四名决赛中球队B赢了球队D。

如果A排名第1，即情况1和情况2综合在一起的情况。

那么，4m支球队的全排列为(4m)!，符合A、B、C和D各自从有m支球队的小组里出线的条件的排列数为(4m)!/(m⁴)，同时符合4支球队中A排第1、D排最后的条件的排列数为2∙(4m)!/(m⁴∙4!)。

如果A排名第k，2 ≤ k ≤ m + 1，此时C和A之间有 k – 2支C所在小组的球队，即情况3.1到3.4的情况。

这种情况下，先从m – 1支C所在小组的球队中排出k – 2支放在A的左边，有P(m – 1, k – 2)种可能。此时，排列的前k 位被固定，其中包括C、A和k – 2支c，A的右边还有4m – k支球队。这些球队的全排列为(4m – k)!，考虑B和D的出线、且B排在D的左边，符合条件的排列数一共有(4m – k)!/(m²∙2)。

因此，A排名第k时，符合条件的排列数为P(m – 1, k – 2)∙(4m – k)!/(m²∙2)。

因此，在题目条件下，球队A排名的数学期望即

当m = 1时，问题退化成4支球队A、B、C和D直接进入半决赛，根据半决赛和三四名决赛的结果，A排名的数学期望为4/3，约等于1.333。

当m = 2时，类似于从8强赛开始，A排名的数学期望为29/21，约等于1.381。

当m = 3时，类似于4个小组中各有3支球队，A排名的数学期望为7/5，等于1.400。

当m = 4时，即本题16支球队的情况，A排名的数学期望为55/39，约等于1.410。

可见，随着m的增大，A排名的数学期望也缓慢增加。这是很容易理解的，因为当C排名第一时，参加的球队越多，就可能有越多排名高的球队在C所在小组里被淘汰，A可能的排名就越低。

下面这个问题留给感兴趣的读者，当m趋向于无穷大时，A排名的数学期望是否收敛？如果收敛，它将收敛于多少？

参考出处：

1. https://sqr5.wordpress.com/2023/01/09/%e5%86%b3%e8%b5%9b%e5%89%8d%e7%9a%84%e6%9c%9f%e6%9c%9b/