我们先从一个看起来简单的问题说起：

假设有一枚均匀的硬币，用 Ｈ表示正面，Ｔ表示反面。反复地抛掷这枚硬币会得到一个由 Ｈ 和 T 组成的随机序列。问题是：平均需要掷多少次硬币，才能得到 THTHT 这个模式？

比如说掷硬币的结果是 HTTHTHT，那么总共用了 7 次才得到 THTHT 这个模式。而如果结果是 THHTTHTHT，则总共用了 9 次。

一个令人惊讶的事情是，同样长度的两个模式，它们的首次出现时间的期望是可以不同的。在这个问题中，答案是平均需要掷 42 次才能得到 THTHT 这个模式 ，而要得到 TTTTT 则平均需要掷 62 次。那么为什么会出现这种看起来和直觉不一致的现象呢？这背后又包含了怎样的数学呢？

另一个令人惊讶的事情是，这样一个表述起来很初等的问题解答起来却并不初等。在已知的所有解法中，组合的方法用到的数学工具算是最少的（见 Feller 的名著 "An Introduction to Probability Theory and Its Applications"），但是相当繁琐。我们要介绍的是离散鞅理论的方法，这个方法非常漂亮精彩，和本系列的其它例子一样，展示了抽象的鞅理论其实有着丰富多彩的应用。

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

解：鞅方法的核心是模拟一个赌博场景，这个场景会提供我们想要的鞅。假设有一个赌徒，怀里揣着一元钱来到一家赌场。他幻想自己能够赌中 THTHT 这个序列。

第一天，他押上这一元钱，赌第一次掷硬币的结果是 T。如果赌错了，空着手回家，赌博结束；如果赌对了，那么可以得 2 元钱（资金翻番），然后在赌场住下。 第二天，他把 2 元钱全部押上，赌第二次掷硬币的结果是 H。如果赌错了，空手走人；如果赌对了，则可以再次将赌本翻番，得到 4 元钱，继续留在赌场。第三天，他押上全部的 4 元钱，赌第三次掷硬币的结果是 T。同样地，赌错了空手走人，赌赢了可以得到 8 元钱。 第四天，押上这 8 元钱，赌第四次掷硬币的结果是 H。规则和前面一样，赌错了就空手走人，赌对了可以把本钱翻番，得到 16 元钱。第五天，押上全部的 16 元，赌第五次掷硬币的结果是 T。赌错了空手走人，赌对了可以得到 32 元，至此赌博结束。

说起来，这个赌局很像电视节目里的闯关游戏，赌局一共有五关，赌徒要一关一关的闯，中间任何一关输了都要空着手拍屁股走人。

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

我们把一个公平的赌局中，庄家到第 $n$ 时刻累积的净利润 $\{X_n\}_{n=1}^\infty $ 称作鞅序列。数学上的定义是

给定一列随机变量 $\{X_n\}_{n=1}^\infty$ 以及一列递增的 $\sigma-$ 域流 $\{\mathcal{F}_n\}_{n=1}^\infty$，其中 $X_n$ 关于 $\mathcal{F}_n$ 是可测的。若它们满足如下的性质：\[ E[X_{n+1} -X_n| \mathcal{F}_n] =0\quad a.e.\] 则称序列 $\{(X_n,\mathcal{F}_n)\}$ 为一个鞅序列。

现在假设从第 1 天开始，每一天都有一个新赌徒揣着 1 元钱来到赌场，他们的赌局跟上面描述的完全一样，但是不同的赌徒之间的赌局互相独立。仍然设第 $n$ 天的赌局结束后庄家累计净赚了 $X_n$ 元，则 $\{X_n\}$ 仍然构成一个鞅序列。（这是因为一系列公平赌局的叠加仍然是公平赌局）

设 $\tau$ 是在掷硬币过程中首次出现模式 THTHT 的时刻，则 $\tau$ 是一个停时。著名的 Doob 可料停时定理说当 $\tau$ 和 $X_n$ 满足一定的条件时有关键的等式 $E[X_\tau]=E[X_1]$ 成立：

（可料停时定理）设 $\{X_n\}_{n=1}^\infty$ 是一个鞅，$\tau$ 是一个停时。如果 $E[\tau]<\infty$ 并且存在常数 $K$ 使得 $|X_n-X_{n-1}|\leq K$ 对任何 $n$ 都几乎处处成立，则\[E[X_\tau]=E[X_1].\]

$\{X_n\}$ 是有界增量的，这一点很显然。而 $\tau$ 被一个几何随机变量所控制，因此 $E[\tau]<\infty$（连续 5 次实验成功的概率为 1/32，把时间以长度为 5 切开即可得证）。因此在我们的问题中，$E[X_\tau]=E[X_1]$ 是成立的。

现在 $X_\tau=\tau-W$。这里第 $\tau$ 天为止庄家总共收取了赌徒 $\tau$ 元钱，$W$ 表示前 $\tau$ 天赌徒总共赢走的钱。这里的关键在于 $W$ 不是一个随机变量，而是一个可计算的常数！

我们仔细分析一下当第 $\tau$ 天结束的时候，哪些赌徒能够赢钱，赢了多少钱。首先能赢钱的赌徒都是留在赌场里的，那些已经走人的赌徒都是空着手走的，所以只有第 $\tau-4$ 到第 $\tau$ 天来赌场的赌徒还有可能留在赌场。这其中，第 $\tau-4$ 天来的赌徒最幸运，赌对了全部的序列，可以得 32 元；第 $\tau-2$ 天来的赌徒也不错，他赌对了前三个，可以得 8 元，第 $\tau$ 天来的赌徒只玩了一局，他赌对了第一个，可以得 2 元，因此庄家一共付给赌徒的钱是 $W =32+8+2=42$ 元，因此\[E[\tau] = W =42.\]

第 $\tau-2$ 天来的赌徒最有意思：他赌的明明是 THTHT 这个序列的前三个 THT（前缀），可是由于 THT 也恰好是 THTHT 的后缀，因此当 $\tau$ 时刻来临时他是一个能赢钱的幸运儿！同理，单个的 T也同时是 THTHT 的前缀和后缀，因此最后一天来的赌徒能赢钱。当然，THTHT 同时是自身的前缀和后缀，所以第 $\tau-4$ 天来的赌徒能赢钱。

这个道理完全适用于一般的模式的首次出现时间：设 $P=(a_1,a_2,\cdots,a_m)$ 是一个给定的由 T 和 H 组成的模式，我们计算它的全部既是前缀又是后缀的子序列的长度，设为 $l_1,\cdots,l_r$，则 P 的首次出现时间 $\tau$ 的期望为

\[ E[\tau] = 2^{l_1}+\cdots+2^{l_r}.\]

再举个例子：HHHHH 的每一个前缀都同时是它的后缀，因此它的首次出现时间的期望最大，为\[E[\tau] = 2^5+2^4+2^3+2^2+2^1 = 62.\]

因此一个模式的首次出现时间完全由它的自匹配的程度决定。

接下来我们要算一个更复杂点的量：$\tau$ 的生成函数

\[ E[s^\tau] =\sum_{n=1}^\infty P(\tau=n)s^n.\]

$\tau$ 的生成函数当然给出了 $\tau$ 的全部信息，知道它你就知道了 $\tau$ 取每一个值的概率，因此在概率论中计算离散随机变量的生成函数是很重要的问题。

我们只需要把前面的赌博序列稍作修改即可：假设第 $n$ 天来的赌徒怀里揣的钱是 $s^n$，这里 $0<s< 1$。每个赌徒的赌局仍然保持公平。这样的话当第 $\tau$ 天来临时，庄家总共收取了赌徒的钱为

\[ s+s^2+\cdots+s^\tau = s \frac{s^\tau-1}{s-1}.\]

赌徒赚的钱为（仍然是那三个人在赚钱，只不过赚的钱数变了）

\[ W = 32 s^{\tau-4}+8 s^{\tau-2} +2s^\tau = s^\tau (\frac{32}{s^4} + \frac{8}{s^2}+2)=s^\tau W(s).\]

所以仍然根据可料停时定理，\[ E[ s \frac{s^\tau-1}{s-1} - s^\tau W(s)]=0.\]

注意 $W(s)$ 不是随机变量，是一个常数！解得

\[ E[s^\tau ]= (1+\frac{1-s}{s} W(s))^{-1}.\]

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

多个模式的首次出现时间

这次我们要考虑更复杂的问题。仍然假设掷的是一枚均匀的硬币，我们想计算在得到的随机序列中首次出现 THH 和 HHH 中某一个的期望时间。也就是说，设 $\tau_1$ 为 THH 的首次出现时间， $\tau_2$ 为 HHH 的首次出现时间，我们想计算 \[\tau=\min\{\tau_1,\tau_2\}\] 的期望。不仅如此，我们还想计算

\[\left\{\begin{array}{l} p_1=P(\tau=\tau_1),\\ p_2=P(\tau=\tau_2).\end{array}\right.\]

即 THH 和 HHH 各自先于对方出现的概率。为此要先给一个定义：

定义：设 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 的首次出现时间 $E[\tau]$，这值又叫做 A 的自匹配指数。

当 A=THH，B=HHH 时，A 的后缀中 H 和 HH 是 B 的前缀，B 的后缀中没有一个是 A 的前缀，因此

\[ A\ast A = 8,\ A\ast B =6,\ B\ast A =0 ,\ B\ast B = 14.\]

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

引理：如果已知在掷硬币的结果中得到的结果是以模式 A 开头的，那么距离模式 B 出现还需要等待的时间的期望为 \[E[\tau_{AB}] = B\ast B -A\ast B.\]

引理的证明：仍然是采用前面的赌博序列的方法， 每天来的赌徒赌的是模式 B。只不过这个时候我们已经知道了前 $m$ 次赌博的结果（假设模式 A 的长度为 $m$）。前 $m$ 天庄家要付给赌徒 $A\ast B$ 元钱。但是由于赌局始终是公平的，所以庄家从第 $m+1$ 天起，直到模式 $B$ 出现的这段时间内，其净利润的期望应该是 0。这段时间长为 $\tau_{AB}$ ，因此庄家要收赌徒 $\tau_{AB}$ 元。但是 $m+1$ 天起至模式 B 出现这段时间庄家付给赌徒的钱等于第一天起至模式 B 出现的时间里庄家付给赌徒的钱减去第一天起至第 $m$ 天里庄家付给赌徒的钱，是 $B\ast B -A\ast B$，所以

\[ E[\tau_{AB}] = B\ast B - A\ast B. \]

引理证毕。

我们来叙述并证明一个一般的结论：

定理：设 $A_1$, $A_2$, $\cdots$, $A_m$ 是 $m$ 个事先给定的且两两互不嵌套的模式，$\tau_i$ 为模式 $A_i$ 的首次出现时刻，$\tau=\min\{\tau_1,\cdots,\tau_m\}$. $p_i=P(\tau=\tau_i)$. 记矩阵\[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 =E[\tau]\mathbf{1}.\]

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

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

有了 $Y$ 和 $E[\tau]$ 自然立刻就得到了 $\pi$。

下面来证明定理的结论：我们有

\[ E[\tau_i] = E[\tau] + E[\tau_i-\tau] =E[\tau] +\sum_{j=1}^m p_jE[\tau_i-\tau|\tau=\tau_j].\]

根据前面的引理，

\[ E[\tau_i-\tau|\tau=\tau_j] = A_i\ast A_i-A_j\ast A_i,\]

因此\[ A_i\ast A_i=E[\tau]+A_i\ast A_i-\sum_{j=1}^np_j A_j\ast A_i.\]

这就证明了定理。

在只有两个模式 A 和 B 的情形，如果一个模式先于另一个出现，就称该模式获胜。这个时候我们可以解出二者各自获胜的概率的表达式来：

推论：设 A，B 是两个给定模式，互不为对方的连续子序列，则模式 B 和模式 A 的获胜概率之比为 $(A\ast A-A\ast B):(B\ast B-B\ast A)$。

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Penny 游戏

文章最后来介绍 Penney 游戏及其中的反直觉概率。

Penney 游戏是两个玩家 A 和 B 的博弈游戏，它仍然以掷硬币为工具：两人事先各自选择一个长为 3 的模式，比如说 A 选择 HHH； B 选择 THH。在掷硬币的过程中若模式 HHH 先出现则玩家 A 获胜；反之若模式 THH 先出现则玩家 B 获胜。我们已经介绍了计算 A 和 B 获胜的概率之比的方法。在这个例子中，B 获胜的概率为 7/8。这是 Penney 游戏的第一个反直觉现象：同样长度的两个序列，不但首次出现的时间期望可以不同，其各自首次出现的概率也未必相同。

不仅如此，实际上不论玩家 A 如何选择他的模式，玩家 B 总可以选择一个相应的模式使得自己有更大的获胜概率，即后选择模式的玩家 B 有更优势的策略（注意不是必胜策略，而是概率意义下的更优策略）。换言之，不存在对玩家 A 来说最优的选择。维基百科的表格给出了玩家 A 的各种选择以及玩家 B 相应的获胜对策。

这里体现了 Penney 游戏的非传递博弈性质：设 $X,Y,Z$ 是 Penney 游戏的三个博弈策略，则 $X$ 优于 $Y$ 和 $Y$ 优于 $Z$ 不能推出 $X$ 优于 $Z$！

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

参考文献

1. Li，S. (1980). A martingale approach to the study of occurrence of sequence patterns in repeated experiments，The Annals of Probability， 8， 1171-1176. 下载

2. Williams，D. (1991). Probability with martingales，Cambridge University Press, Cambridge.

3. Pozdnyakov，V. and Steele，J.M. Martingale methods for patterns and scan statistics. 下载

模式中的反直觉概率