模式的等待时间与反直觉概率

2011-06-03

鞅和赌博序列
多个模式的等待时间与获胜概率
Penney 游戏
还有更不可思议的事情
References

著名概率学家 Feller 在他的名著 “An introduction to probability and its applications” 中提到了这样一个实验：

问题：重复抛掷一枚均匀的硬币，用 H 代表正面向上，T 代表背面向上，一直到连续出现 6 次 H 为止。这里连续 6 个 Ｈ 组成的模式记作 HHHHHH，所需要抛掷硬币的次数叫做等待时间。等待时间是一个随机变量，最小值是 6，最大值可以是无限。Feller 问：等待时间的期望是多少？

这个问题可以用 Markov 链来解，但是非常繁琐。香港中文大学李硕彦教授在他的论文 (Li 1980) 中用离散鞅的知识给出了一个简洁而巧妙的解法，本文就来介绍他的方法。

鞅和赌博序列

我们用 HTHT 这个模式为例子，来演示如何求出它的平均等待时间。

假设有一个赌徒，怀里揣着 1 元钱来到一家赌场，他的目标是赌中 HTHT 这个序列。

第一天，他押上这 1 元钱，赌第一次掷硬币的结果是 H。如果他赌错了就得空手走人，而赌对的话则可以赢得 2 元（资金翻番）并留在赌场。
第二天，他押上全部的 2 元，赌第二次掷硬币的结果是 Ｔ。跟以前一样，赌错了空手走人，赌对了的话则资金翻番变成 4 元并留在赌场。
第三天，他押上全部的 4 元，赌第三次掷硬币的结果是 H。赌错了空手走人，赌对了的话则资金翻番变成 8 元并留在赌场。
第四天，他押上全部的 8 元，赌第四次掷硬币的结果是 T。赌错了空手走人，赌对了资金翻番变成 16 元，赌局结束。

这个赌局很像电视节目里的闯关游戏，赌局一共有 4 关，赌徒要一关一关的闯，中间任何一关输了都要空手走人。

赌局对赌徒和庄家来讲都是公平的：大家在期望的意义下都是不赔不赚。每一天，赌徒都以 1/2 的概率输光赌本，也以 1/2 的概率将赌本翻番。

现在假设有一个赌博团伙，他们每天都派一个人到赌场赌博，每个赌徒的赌局与上面的描述相同，不同的赌徒的赌局互相独立。我们用 ${X_{n}, n = 0, 1, 2, \dots}$ 表示第 $n$ 天结束以后这个团伙的「净收益」，其中 $X_{0} = 0$ 。由于赌局是公平的，因此 ${X_{n}}$ 是一个鞅。

设 $τ$ 是模式 HTHT 的等待时间，则 $τ$ 是一个停时。不难验证 ${X_{n}}$ 和 $τ$ 满足 Doob 可料停时定理的条件

Doob 可料停时定理. 设 ${X_{n}, n = 0, 1, 2, \dots}$ 是一个鞅， $τ$ 是停时且满足

$E τ < \infty$ ，
存在常数 $M$ 使得 $| X_{n + 1} - X_{n} | \leq M$ 对任何 $n$ 都几乎处处成立。

则 $E X_{τ} = E X_{0}$ 。

因此在我们的问题中 $E X_{τ} = E X_{0} = 0$ 。

显然 $X_{τ} = W - τ$ ，这里 $W$ 表示第 $τ$ 天结束时留在赌场内的赌徒的资金之和，要减去 $τ$ 是因为第 $τ$ 天结束时赌博团伙总共派出了 $τ$ 个赌徒，他们投入的赌本总共是 $τ$ 元。根据上面的讨论，有 $E W = E τ$ 成立。这里的关键在于 $W$ 不是一个随机变量，而是一个可以算出来的常数！

$τ$ -3	$τ$ -2	$τ$ -1	$τ$
H	T	H	T

我们仔细分析一下当第 $τ$ 天结束的时候，哪些赌徒还在赌场内，他们各自有多少钱。由于 $τ$ 是首次有某个赌徒闯关成功的时刻，所以只有第 $τ - 3$ 到第 $τ$ 天来赌场的这 4 个赌徒还有可能留在赌场，更早的赌徒都输光走人了。

第 $τ - 3$ 天来的赌徒是那个闯关成功的幸运儿，他有 16 元；
第 $τ - 2$ 和第 $τ$ 天来的两个赌徒由于赌的是 H 但结果是 T，所以他们当天就走人了；
第 $τ - 1$ 天来的赌徒连续赌对了 HT，他还有 4 元。

因此赌徒们总共有 $W = 16 + 4 = 20$ 元，即 $E τ = 20$ 。

这里第 $τ - 1$ 天来的赌徒最有趣：他赌的明明是 HTHT 的前缀 HT，但是由于 HT 恰好也是 HTHT 的后缀，因此他也能赢到钱！

这个推理完全适用于一般的情形：设 $P = (a_{1}, a_{2}, \dots, a_{m})$ 是一个给定的由 T 和 H 组成的模式，我们计算它的全部既是前缀又是后缀的子序列的长度，设为 $l_{1}, \dots, l_{r}$ ，则 $P$ 的等待时间 $τ$ 的期望为 $E τ = 2^{l_{1}} + \dots + 2^{l_{r}} .$

回到开头的例子：HHHHHH 的每一个前缀都同时是它的后缀，因此它的平均等待时间为 $2^{6} + 2^{5} + 2^{4} + 2^{3} + 2^{2} + 2^{1} = 126.$ 所以一个模式的平均等待时间完全由它的自匹配的程度决定。

把上面的方法稍作修改，还可以用来计算 $τ$ 的生成函数 $E [s^{τ}] = \sum_{n = 1}^{\infty} P (τ = n) s^{n} .$ 为此只要假设第 $n$ 天来的赌徒怀里揣的钱是 $s^{n} (0 < s < 1)$ 即可，这里不再赘述。

多个模式的等待时间与获胜概率

假设同时有多个模式 $A_{1}, \dots, A_{m}$ 加入「赛跑」，我们想计算它们各自胜出的概率。用数学公式表示，就是设 $A_{i}$ 的等待时间为 $τ_{i}$ ，令 $τ = min {τ_{1}, \dots, τ_{m}},$ 则 $τ$ 表示赛跑过程中冠军「撞线」的时刻，又令 $p_{i} = P (τ = τ_{i})$ ，则 $p_{i}$ 表示模式 $A_{i}$ 「夺冠」的概率。我们想计算出每个 $p_{i}$ 的值来。

为此先给一个定义：

定义. 设 $A$ 和 $B$ 是两个给定的模式，且 $A$ 和 $B$ 都不是对方的连续子序列。我们计算所有既是 $A$ 的后缀又是 $B$ 的前缀的全部子序列，设它们的长度为 $l_{1}, \dots, l_{r}$ ，定义 $A$ 和 $B$ 的匹配指数为 $A * B = 2^{l_{1}} + \dots + 2^{l_{r}} .$ 如果 $A$ 的任何后缀都不是 $B$ 的前缀则 $A * B$ 定义为 0。特别当 $A = B$ 时， $A * A$ 就是前面计算的 $A$ 的平均等待时间，这个值又叫做 $A$ 的自匹配指数。

我们要证明这样一个引理：

引理. 如果已知掷硬币的结果是以模式 $A$ 开头的，那么距离模式 $B$ 出现还需要等待的时间的期望为 $E τ_{A B} = B * B - A * B .$

引理的证明：仍然是采用赌博序列的方法，每天来的赌徒赌的是模式 $B$ ，只不过这个时候我们已经知道了前 $k$ 次赌博的结果是模式 $A$ （假设序列 $A$ 的长度为 $k$ ），所以不难算出前 $k$ 天赌博团伙的总资金为 $A * B$ 元。由于赌局始终是公平的，所以从 $k + 1$ 天起，直到模式 $B$ 出现的这 $τ_{A B}$ 天里，赌徒们的净收益期望应该是 0。到模式 $B$ 出现时，赌徒们的资金将变成 $B * B$ 元，所以这 $τ_{A B}$ 天中赌徒们的资金增加了 $B * B - A * B$ 元，扣除他们的投入 $τ_{A B}$ 元，就是这段时间的净收益，其期望为 0： $E [B * B - A * B - τ_{A B}] = 0.$ 引理证毕。

接下来叙述并证明一个一般的结论：

定理. 设 $A_{1}$ , $A_{2}$ , $\dots$ , $A_{m}$ 是 $m$ 个事先给定的且两两互不嵌套的模式，记矩阵 $M = (\begin{matrix} A_{1} * A_{1} & A_{1} * A_{2} & \dots & A_{1} * A_{m} \\ A_{2} * A_{1} & A_{2} * A_{2} & \dots & A_{2} * A_{m} \\ \dots & \dots & \dots & \dots \\ A_{m} * A_{1} & A_{m} * A_{2} & \dots & A_{m} * A_{m} \end{matrix}),$ $π = (p_{1}, p_{2}, \dots, p_{m})^{T}, 1 = (1, 1, \dots, 1)^{T},$ 则 $M$ 是可逆矩阵，并且 $M π = E [τ] 1 .$

在证明定理之前，先说说怎样根据定理的结论来计算 $E [τ]$ 和概率分布向量 $π$ 。首先解出 $M Y = 1$ 的解 $Y = (y_{1}, y_{2}, \dots, y_{m})^{T}$ 来。根据可逆矩阵解的唯一性，必然有 $π = E [τ] Y$ 。但是 $π$ 是一个概率分布，它的所有分量之和为 1，因此 $E [τ] = \frac{1}{y_{1} + y_{2} + \dots + y_{m}} .$

$M$ 是可逆矩阵这一点是需要证明的，本文就省略了。事实上 $A_{i}$ 之间两两互不嵌套这个条件就可以保证 $M$ 是可逆的。

有了 $Y$ 和 $E [τ]$ 自然立刻就得到了 $π$ 。

定理的证明：我们有 $E [τ_{i}] = E [τ] + E [τ_{i} - τ] = E [τ] + \sum_{j = 1}^{m} p_{j} E [τ_{i} - τ | τ = τ_{j}] .$ 根据引理， $E [τ_{i} - τ | τ = τ_{j}] = A_{i} * A_{i} - A_{j} * A_{i},$ 因此 $A_{i} * A_{i} = E [τ] + A_{i} * A_{i} - \sum_{j = 1}^{n} p_{j} A_{j} * A_{i} .$ 这就证明了定理。

Penney 游戏

Penney 游戏是两个玩家 Bob 和 Alice 的博弈游戏，它以掷硬币为工具：游戏开始前，两人各自选择一个长度为 3 的由 H 和 T 组成的模式，比如说 Bob 选择 HHH，Alice 选择 THH，然后掷硬币直到其中一人选择的模式首先出现，先出现的一方获胜。

Penney 游戏有一个独特之处：

假设 Bob 先选择他的序列，则不论 Bob 怎样选，Alice 总可以「针锋相对」地选一个合适的序列，使得自己的获胜概率更高。总而言之，Penney 游戏是所谓的「后发制人，先发者制于人」。

这个有点类似于我们都熟悉的「剪子，石头，布」游戏。在 Penney 游戏中，各种策略循环相克，维基百科中给出了各种情形下二人的获胜概率之比。在这个例子中，Alice 的获胜概率为 7/8。

Penney 游戏是非传递博弈的典型例子：策略 $A$ 优于 $B$ ， $B$ 优于 $C$ 并不能推出 $A$ 优于 $C$ 。

在只有两个模式 $A$ 和 $B$ 的情形，二者各自获胜的概率有一个很简单的表达式：

推论. 设 $A, B$ 是两个给定的序列，它们互不为对方的连续子序列，则序列 $B$ 和序列 $A$ 的获胜概率之比为 $p_{B} : p_{A} = (A * A - A * B) : (B * B - B * A)$ 。

还有更不可思议的事情

我们已经介绍了怎样计算一个模式的平均等待时间，以及多个模式同时「赛跑」时各自的获胜概率。我们现在来看看 THTH 和 HTHH 比赛的结果如何。

首先不难算出 THTH 的平均等待时间是 20，HTHH 的平均等待时间是 18，也就是说 THTH 跑的慢一些，HTHH 跑的快一些，这是不是意味着让它俩赛跑的话，HTHH 获胜的概率更大呢？

答案是否定的，这其实是一个一面倒的竞赛：

看起来慢一些的模式 THTH，其与 HTHH 的胜算之比为 9 比 5，即平均每 14 场赛跑，THTH 会赢 9 场，而貌似快一些的 HTHH 倒只赢 5 场。

为什么会出现这种反直觉的现象呢？其实「跑得慢」和「赢得多」并不矛盾。我们随便看一个由 H 和 T 组成的随机序列：

HHTHTHHTHTHHTTTHHTHHHHTTHHTTHTTHTHHTHHTHHTHHHHTTHTTTTTTHTTHTHTTHHTHHHHHHTTHTHHTHTHHTTTTTHTTHHHHHHTHHHTTTHTTTHTTTHHHTHHTHTHTTTHTTHTTHTHHTHHTTHTHHHTTHH …

其中分别用红色和绿色标记了模式 THTH 和 HTHH 的出现的位置。注意到任何绿色 H 后面连续的三个字符中绝对不会出现红色 H，而大约一半的红色的 H 后面紧跟一个绿色的 H。所以从一个随机序列中任选一点作为起点开始比赛，那么在 THTH 先撞线的比赛中，第二个撞线的绿色 HTHH 往往会只落后一个身位，但是在绿色 HTHH 先撞线的比赛中，红色的 THTH 至少要落后四个身位以上。

用足球来类比，领先一个身位就好比取得一个净胜球。THTH 击败 HTHH 的方法类似「一比零主义」：THTH 一半的赢球是靠一比零拿下的，而且每次输球都要输四个以上的球，所以总净胜球为负（平均等待时间长）。但由于赢的场数多，积分反而领先。

References

Li, Shuo-Yen Robert. 1980. “A Martingale Approach to the Study of Occurrence of Sequence Patterns in Repeated Experiments.” The Annals of Probability 8 (6): 1171–76. https://doi.org/10.1214/aop/1176994578.

上一篇：三质点弹簧系统的简正模式

下一篇：洛奇绵羊问题