朝花夕拾

轻飘飘的旧时光就这么溜走 转头回去看看时已匆匆数年

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

2011-06-03


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

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

这个问题可以用 Markov 链来解,但是非常繁琐。香港中文大学李硕彦教授在他的论文

A Martingale Approach to the Study of Occurrence of Sequence Patterns in Repeated Experiments.

中用离散鞅的知识给出了一个简洁而巧妙的解法,本文就来介绍他的方法。

鞅和赌博序列

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

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

这个赌局很像电视节目里的闯关游戏,赌局一共有 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\) 是停时且满足

  1. \(\mathbb{E}\tau < \infty\)

  2. 存在常数 \(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\) 元,根据上面的讨论,有 \(\mathbb{E}W=\mathbb{E}\tau\) 成立。这里的关键在于 \(W\) 不是一个随机变量,而是一个可以算出来的常数!

我们仔细分析一下当第 \(\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)\) 是一个给定的由 TH 组成的模式,我们计算它的全部既是前缀又是后缀的子序列的长度,设为 \(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 的由 HT 组成的模式,比如说 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)\)

还有更不可思议的事情

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

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

答案是否定的,这其实是一个一面倒的竞赛:

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

为什么会出现这种反直觉的现象呢? 其实 "跑得慢" 和 "赢得多" 并不矛盾,我们随便看一个由 HT 组成的比较长一点的随机序列:

HHTHTHHTHTHHTTTHHTHHHHTTHHTTHTTHTHHTHHTHHTHHHHTTHTTTTTTHTT HTHTTHHTHHHHHHTTHTHHTHTHHTTTTTHTTHHHHHHTHHHTTTHTTTHTTTHHHT HHTHTHTTTHTTHTTHTHHTHHTTHTHHHTTHH ...

其中分别用红色和绿色标记了模式 THTHHTHH 的出现的位置。理论上由于是随机序列,所以红色的 H 和绿色的 H 的个数应该大致相等,各占序列总长度的十六分之一。但是二者出现的规律不同:任何绿色 H 后面连续的三个字符中绝对不会出现红色 H,而大约一半的红色的 H 后面紧跟一个绿色的 H。所以从一个随机序列中任选一点作为起点开始比赛,那么在红色 H 先撞线的比赛中,第二个撞线的绿色 H 往往会只落后一个身位,但是在绿色 H 先撞线的比赛中,红色的 H 至少要落后四个身位以上。总而言之,THTH 击败 HTHH 的方法就是 "小胜多胜",在 THTH 先撞线的比赛中,THTH 只领先 HTHH 很少,而 HTHH 先撞线的比赛中,HTHH 可以领先 THTH 很多,于是平均下来虽然 THTH 赢的多一些,但是平均耗时反倒长一些。