模式的等待时间与反直觉概率
著名概率学家 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,\ldots\}\) 表示第 \(n\) 天结束以后这个团伙的「净收益」，其中 \(X_0=0\)。由于赌局是公平的，因此 \(\{X_n\}\) 是一个鞅。
设 \(\tau\) 是模式 HTHT
的等待时间，则 \(\tau\)
是一个停时。不难验证 \(\{X_n\}\) 和
\(\tau\) 满足 Doob
可料停时定理 的条件
Doob 可料停时定理. 设 \(\{X_n, n=0,1,2,\ldots\}\) 是一个鞅，\(\tau\) 是停时且满足
- \(\mathbb{E}\tau < \infty\)，
- 存在常数 \(M\) 使得 \(|X_{n+1}-X_{n}|\leq M\) 对任何 \(n\) 都几乎处处成立。
则 \(\mathbb{E}X_\tau = \mathbb{E}X_0\)。
因此在我们的问题中 \(\mathbb{E}X_\tau = \mathbb{E}X_0 = 0\)。
显然 \(X_\tau=W-\tau\)，这里 \(W\) 表示第 \(\tau\) 天结束时留在赌场内的赌徒的资金之和，\(\tau\) 表示第 \(\tau\) 天结束时赌博团伙总共派出了 \(\tau\) 个赌徒，他们带入赌场的赌本总共是 \(\tau\) 元。根据上面的讨论，有 \(\mathbb{E}W=\mathbb{E}\tau\) 成立。这里的关键在于 \(W\) 不是一个随机变量，而是一个可以算出来的常数！
我们仔细分析一下当第 \(\tau\)
天结束的时候，哪些赌徒还在赌场内，他们各自有多少钱。由于 \(\tau\)
是首次有某个赌徒闯关成功的时刻，所以只有第 \(\tau-3\) 到第 \(\tau\) 天来赌场的这 4
个赌徒还有可能留在赌场，更早的赌徒都输光走人了。其中第 \(\tau-3\)
天来的赌徒最幸运，赌对了全部的序列，他还有 16 元；第 \(\tau-1\) 天来的赌徒也不错，他赌对了
HT，他还有 4 元，因此赌徒们总共有 \(W=16+4=20\) 元，即 \(\mathbb{E}\tau=20\)。
这里第 \(\tau-1\)
天来的赌徒最有趣：他赌的明明是 HTHT 的前缀
HT，但是由于 HT 恰好也是 HTHT
的后缀，因此他也能赢到钱！
这个推理完全适用于一般的情形：设 \(P=(a_1,a_2,\cdots,a_m)\) 是一个给定的由
T 和 H
组成的模式，我们计算它的全部既是前缀又是后缀的子序列的长度，设为 \(l_1,\cdots,l_r\)，则 \(P\) 的等待时间 \(\tau\) 的期望为 \[\mathbb{E}\tau =
2^{l_1}+\cdots+2^{l_r}.\]
回到开头的例子：HHHHHH
的每一个前缀都同时是它的后缀，因此它的平均等待时间为 \[2^6+2^5+2^4+2^3+2^2+2^1 = 126.\]
所以一个模式的平均等待时间完全由它的自匹配的程度决定。
把上面的方法稍作修改，还可以用来计算 \(\tau\) 的生成函数 \[ \mathbb{E}[s^\tau] =\sum_{n=1}^\infty \mathbb{P}(\tau=n)s^n.\] 为此只要假设第 \(n\) 天来的赌徒怀里揣的钱是 \(s^n(0<s<1)\) 即可，这里不再赘述。
多个模式的等待时间与获胜概率
假设同时有多个模式 \(A_1,\ldots,A_m\) 加入「赛跑」，我们想计算它们各自胜出的概率。用数学公式表示，就是设 \(A_i\) 的等待时间为 \(\tau_i\)，令 \[\tau=\min\{\tau_1,\ldots,\tau_m\},\] 则 \(\tau\) 表示赛跑过程中冠军「撞线」的时刻，又令 \(p_i=\mathbb{P}(\tau=\tau_i)\)，则 \(p_i\) 表示模式 \(A_i\) 「夺冠」 的概率。我们想计算出每个 \(p_i\) 的值来。
为此先给一个定义：
定义. 设 \(A\) 和 \(B\) 是两个给定的模式，且 \(A\) 和 \(B\) 都不是对方的连续子序列。我们计算所有既是 \(A\) 的后缀又是 \(B\) 的前缀的全部子序列，设它们的长度为 \(l_1,\cdots,l_r\)，定义 \(A\) 和 \(B\) 的匹配指数为 \[A\ast B = 2^{l_1}+\cdots+2^{l_r}.\] 如果 \(A\) 的任何后缀都不是 \(B\) 的前缀则 \(A\ast B\) 定义为 0。特别当 \(A=B\) 时，\(A\ast A\) 就是前面计算的 \(A\) 的平均等待时间，这个值又叫做 \(A\) 的自匹配指数。
我们要证明这样一个引理 ：
引理. 如果已知掷硬币的结果是以模式 \(A\) 开头的，那么距离模式 \(B\) 出现还需要等待的时间的期望为 \[\mathbb{E}\tau_{AB} = B\ast B -A\ast B.\]
引理的证明：仍然是采用赌博序列的方法，每天来的赌徒赌的是模式 \(B\)，只不过这个时候我们已经知道了前 \(k\) 次赌博的结果是模式 \(A\)（假设序列 \(A\) 的长度为 \(k\)），所以不难算出前 \(k\) 天赌博团伙的总资金为 \(A\ast B\) 元。由于赌局始终是公平的，所以从 \(k+1\) 天起，直到模式 \(B\) 出现的这 \(\tau_{AB}\) 天里，赌徒们的净收益期望应该是 0。到模式 \(B\) 出现时，赌徒们的资金将变成 \(B\ast B\) 元，所以这 \(\tau_{AB}\) 天中赌徒们的资金增加了 \(B\ast B-A\ast B\) 元，扣除他们的投入 \(\tau_{AB}\) 元，就是这段时间的净收益，其期望为 0： \[\mathbb{E} [B\ast B-A\ast B -\tau_{AB}]=0.\] 引理证毕。
接下来叙述并证明一个一般的结论：
定理. 设 \(A_1\), \(A_2\), \(\cdots\), \(A_m\) 是 \(m\) 个事先给定的且两两互不嵌套的模式，记矩阵 \[M=\begin{pmatrix} A_1\ast A_1 & A_1\ast A_2&\cdots& A_1\ast A_m\\ A_2\ast A_1&A_2\ast A_2&\cdots& A_2\ast A_m\\ \cdots&\cdots&\cdots&\cdots\\ A_m\ast A_1&A_m\ast A_2&\cdots&A_m\ast A_m\end{pmatrix},\] \[\pi = (p_1,p_2,\cdots,p_m)^T,\quad \mathbf{1}=(1,1,\cdots,1)^T,\] 则 \(M\) 是可逆矩阵，并且 \[M\pi =\mathbb{E}[\tau]\mathbf{1}.\]
在证明定理之前，先说说怎样根据定理的结论来计算 \(\mathbb{E}[\tau]\) 和概率分布向量 \(\pi\)。首先解出 \(MY=\mathbf{1}\) 的解 \(Y=(y_1,y_2,\cdots,y_m)^T\) 来。根据可逆矩阵解的唯一性，必然有 \(\pi=\mathbb{E}[\tau]Y\)。但是 \(\pi\) 是一个概率分布，它的所有分量之和为 1，因此 \[\mathbb{E}[\tau] =\frac{1}{y_1+y_2+\cdots+y_m}.\]
\(M\) 是可逆矩阵这一点是需要证明的，本文就省略了。事实上 \(A_i\) 之间两两互不嵌套这个条件就可以保证 \(M\) 是可逆的。
有了 \(Y\) 和 \(\mathbb{E}[\tau]\) 自然立刻就得到了 \(\pi\)。
定理的证明：我们有 \[\mathbb{E}[\tau_i] = \mathbb{E}[\tau] + \mathbb{E}[\tau_i-\tau] =\mathbb{E}[\tau] +\sum_{j=1}^m p_j\mathbb{E}[\tau_i-\tau|\tau=\tau_j].\] 根据引理， \[\mathbb{E}[\tau_i-\tau|\tau=\tau_j] = A_i\ast A_i-A_j\ast A_i,\] 因此 \[A_i\ast A_i=\mathbb{E}[\tau]+A_i\ast A_i-\sum_{j=1}^np_j A_j\ast 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\ast A-A\ast B):(B\ast B-B\ast 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。所以从一个随机序列中任选一点作为起点开始比赛，那么在红色
H 先撞线的比赛中，第二个撞线的绿色 H
往往会只落后一个身位，但是在绿色 H 先撞线的比赛中，红色的
H 至少要落后四个身位以上。
用足球来类比，领先一个身位就好比取得一个净胜球。净胜球少和积分领先并不矛盾。THTH
击败 HTHH 的方法类似「一比零主义」：虽然平均下来
THTH
耗时长一些（每场净胜球少），但积分是领先的（赢的场数多）。