模式的等待时间与反直觉概率
著名概率学家 Feller 在他的名著 “An Introduction to Probability Theory and Its Applications” 中提到了这样一个实验：
问题： 重复抛掷一枚均匀的硬币，用 \(\texttt{H}\) 代表正面向上，\(\texttt{T}\) 代表背面向上，一直到连续出现 6 次 \(\texttt{H}\) 为止。这里连续 6 个 \(\texttt{H}\) 组成的模式记作 \(\texttt{HHHHHH}\)，所需要抛掷硬币的次数叫做等待时间。等待时间是一个随机变量，最小值是 6，最大值可以是无限。Feller 问：等待时间的期望是多少？
这个问题可以用 Markov 链来解，但是非常繁琐。香港中文大学李硕彦教授在他的论文 (Li 1980) 中用离散鞅的知识给出了一个简洁而巧妙的解法，本文就来介绍他的方法。
鞅和赌博序列
我们用 \(\texttt{HTHT}\) 这个模式为例子，来演示如何求出它的平均等待时间。
假设有一个赌徒，怀里揣着 1 元钱来到一家赌场，他的目标是赌中 \(\texttt{HTHT}\) 这个序列。
第一天，他押上这 1 元钱，赌第一次掷硬币的结果是 \(\texttt{H}\)。如果他赌错了就得空手走人，而赌对的话则可以赢得 2 元 （资金翻番） 并留在赌场。
第二天，他押上全部的 2 元，赌第二次掷硬币的结果是 \(\texttt{T}\)。跟以前一样，赌错了空手走人，赌对了的话则资金翻番变成 4 元并留在赌场。
第三天，他押上全部的 4 元，赌第三次掷硬币的结果是 \(\texttt{H}\)。赌错了空手走人，赌对了的话则资金翻番变成 8 元并留在赌场。
第四天，他押上全部的 8 元，赌第四次掷硬币的结果是 \(\texttt{T}\)。赌错了空手走人，赌对了资金翻番变成 16 元，赌局结束。
这个赌局很像电视节目里的闯关游戏，赌局一共有 4 关，赌徒要一关一关的闯，中间任何一关输了都要空手走人。
赌局对赌徒和庄家来讲都是公平的：大家在期望的意义下都是不赔不赚。每一天，赌徒都以 1/2 的概率输光赌本，也以 1/2 的概率将赌本翻番。
现在假设有一个赌博团伙，他们每天都派一个人到赌场赌博，每个赌徒的赌局与上面的描述相同。所有赌徒面对的是同一串抛硬币结果，因此他们的赌局并不相互独立。但是有限个公平赌局的资金之和仍然具有公平性。因此，赌博团伙的总净收益过程是一个鞅。我们用 \(\{X_n,n=0,1,2,\ldots\}\) 表示第 \(n\) 天结束以后这个团伙的「净收益」，\(\{X_n\}\) 是一个鞅。
设 \(\tau\) 是模式 \(\texttt{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\)-3 | \(\tau\)-2 | \(\tau\)-1 | \(\tau\) |
| \(\texttt{H}\) | \(\texttt{T}\) | \(\texttt{H}\) | \(\texttt{T}\) |
我们仔细分析一下当第 \(\tau\) 天结束的时候，哪些赌徒还在赌场内，他们各自有多少钱。由于 \(\tau\) 是首次有某个赌徒闯关成功的时刻，所以只有第 \(\tau-3\) 到第 \(\tau\) 天来赌场的这 4 个赌徒还有可能留在赌场，更早的赌徒都输光走人了。
- 第 \(\tau-3\) 天来的赌徒是那个闯关成功的幸运儿，他有 16 元；
- 第 \(\tau-2\) 和第 \(\tau\) 天来的两个赌徒由于赌的是 \(\texttt{H}\) 但结果是 \(\texttt{T}\)，所以他们当天就走人了；
- 第 \(\tau-1\) 天来的赌徒连续赌对了 \(\texttt{HT}\)，他还有 4 元。
因此赌徒们总共有 \(W=16+4=20\) 元，即 \(\mathbb{E}\tau=20\)。
这里第 \(\tau-1\) 天来的赌徒最有趣：他赌的明明是 \(\texttt{HTHT}\) 的前缀 \(\texttt{HT}\)，但是由于 \(\texttt{HT}\) 恰好也是 \(\texttt{HTHT}\) 的后缀，因此他也能赢到钱！
这个推理完全适用于一般的情形：设 \(P=(a_1,a_2,\cdots,a_m)\) 是一个给定的由 \(\texttt{T}\) 和 \(\texttt{H}\) 组成的模式，我们计算它的全部既是前缀又是后缀的子序列的长度，设为 \(l_1,\cdots,l_r\)，则 \(P\) 的等待时间 \(\tau\) 的期望为 \[\mathbb{E}\tau = 2^{l_1}+\cdots+2^{l_r}.\]
回到开头的例子：\(\texttt{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_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^\mathsf{T}\pi =\mathbb{E}[\tau]\mathbf{1}.\]
在证明定理之前，先说说怎样根据定理的结论来计算 \(\mathbb{E}[\tau]\) 和概率分布向量 \(\pi\)。首先解出 \(M^\mathsf{T}Y=\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\)。
证明：对每个模式 \(A_i\)，我们都安排一个专门押 \(A_i\) 的赌博团伙。所有 \(m\) 个团伙都在每天派出一名新赌徒。
固定 \(i\)。设第一个出现的模式是 \(A_j\)。设押 \(A_i\) 的某个赌徒在第 \(\tau-\ell+1\) 天入场。到第 \(\tau\) 天的抛掷结束时，他一共经历了 \(\ell\) 轮下注。他仍然留在赌场，当且仅当这 \(\ell\) 天的抛掷结果恰好等于 \(A_i\) 的前 \(\ell\) 个字符。
另一方面，既然在时刻 \(\tau\) 首先出现的模式是 \(A_j\)，那么这个赌徒经历的 \(\ell\) 次抛掷结果就是 \(A_j\) 的长度为 \(\ell\) 的后缀。所以这个赌徒仍然留在场内，当且仅当 \(A_i\) 的前缀 \(\ell\) 个字符等于 \(A_j\) 的后缀 \(\ell\) 个字符。
因此在第 \(\tau\) 天押 \(A_i\) 的团伙的总资金为 \(A_j\ast A_i\)，扣除成本 \(\tau\) 元，净收益为 \(A_j\ast A_i-\tau\)。
根据 Doob 可选停止定律，有 \[0 = \sum_{j=1}^m p_j (A_j\ast A_i)-\mathbb{E}\tau.\] 也就是 \[\sum_{j=1}^m p_j (A_j\ast A_i)=\mathbb{E}\tau.\] 写成矩阵形式，就是 \[M^\mathsf{T}\pi = \mathbb{E}\tau\,\mathbf{1}.\]
\(\blacksquare\)
Penney 游戏
Penney 游戏是两个玩家 Bob 和 Alice 的博弈游戏，它以掷硬币为工具：游戏开始前，两人各自选择一个长度为 3 的由 \(\texttt{H}\) 和 \(\texttt{T}\) 组成的模式，比如说 Bob 选择 \(\texttt{HHH}\)，Alice 选择 \(\texttt{THH}\)，然后掷硬币直到其中一人选择的模式首先出现，先出现的一方获胜。
Penney 游戏有一个独特之处：
假设 Bob 先选择他的序列，则不论 Bob 怎样选，Alice 总可以「针锋相对」地选一个合适的序列，使得自己的获胜概率更高。总而言之，Penney 游戏是所谓的「后发制人，先发者制于人」。
如果先手选择 \[A=a_1a_2a_3.\] 后手可以选择 \[B=\overline{a_2}a_1a_2.\] 其中 \(\overline{\texttt{H}}=\texttt{T},\overline{\texttt{T}}=\texttt{H}\)。
例如先手选择 \(\texttt{HHH}\)，那么后手选择 \(\texttt{THH}\)。
这个有点类似于我们都熟悉的「剪子，石头，布」游戏。在 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)\)。
还有更不可思议的事情
我们已经介绍了怎样计算一个模式的平均等待时间，以及多个模式同时「赛跑」时各自的获胜概率。我们现在来看看 \(\texttt{THTH}\) 和 \(\texttt{HTHH}\) 比赛的结果如何。
首先不难算出 \(\texttt{THTH}\) 的平均等待时间是 20，\(\texttt{HTHH}\) 的平均等待时间是 18，也就是说 \(\texttt{THTH}\) 跑的慢一些，\(\texttt{HTHH}\) 跑的快一些，这是不是意味着让它俩赛跑的话，\(\texttt{HTHH}\) 获胜的概率更大呢？
答案是否定的，这其实是一个一面倒的竞赛：
看起来慢一些的模式 \(\texttt{THTH}\)，其与 \(\texttt{HTHH}\) 的胜算之比为 9 比 5，即平均每 14 场赛跑，\(\texttt{THTH}\) 会赢 9 场，而貌似快一些的 \(\texttt{HTHH}\) 倒只赢 5 场。
为什么会出现这种反直觉的现象呢？其实「跑得慢」和「赢得多」并不矛盾。
首先， \[\underbrace{\texttt{THTH}}_{A}\texttt{H}=\texttt{T}\underbrace{\texttt{HTHH}}_{B}.\] 所以当 \(A\) 首先出现以后，只要下一次抛出 \(\texttt{H}\)，概率为 \(1/2\)，\(B\) 就会在一个身位之后出现。
但是反过来，\(B=\texttt{HTHH}\) 的任何非空后缀都不是 \(A=\texttt{THTH}\) 的前缀：
\[\texttt{H}\neq\texttt{T},\quad\texttt{HH}\neq\texttt{TH},\quad\texttt{THH}\neq\texttt{THT}.\] 所以当 \(B\) 首先出现时，\(A\) 至少还需要四次新的抛掷才能出现。
用足球来类比，领先一个身位就好比取得一个净胜球。\(A=\texttt{THTH}\) 击败 \(B=\texttt{HTHH}\) 的方法类似「一比零主义」：\(A\) 一半的赢球是靠一比零拿下的，但是每次输球都要输四个以上，所以总净胜球为负（平均等待时间长）。但由于赢的场数多，积分反而领先。