Recurrent Event

面试中曾经遇到这么一道概率题:

一只猴子随机敲键盘上的 26 个字母, 期望在多少次之后能首次打出 "hulu"?

当时只是直觉觉得答案应该是 , 没有想出很好的做法. 想出来的唯一方法是列一个四元线性方程组, 四个变量定义如下, 有点像 Markov Chain 的感觉:

1. 打出 hulu 的期望次数
2. 已打出 h, 从现在开始算打出 hulu 的期望次数
3. 已打出 hu, 从现在开始算打出 hulu 的期望次数
4. 已打出 hul, 从现在开始算打出 hulu 的期望次数

这四个变量, 每个都可以用其他三个线性组合, 于是就可以解方程了. 不过解四元线性方程的计算量不像是电话面试应该有的... 面试完之后算了算发现确实是 . (经验教训是: 下次遇到这种情况就不停的说思路啊! 把面试官侃晕...)

后来, 直到寒假的时候, 读了 William Feller 的概率论及其应用. 其中一章 Recurrent Event (中译 "循环事件") 给了这一类问题的漂亮的解答.

我们考虑一个有限结果的重复实验, 每次的结果可能是 . 是一个有限结果序列的可判定属性. 我们姑且称 是一个事件 (Event), 称它在序列 的第 位 "发生", 意思为 具有属性

若属性 满足以下两个条件, 则称其定义了一个 Recurrent Event:

• 在 的第 和第 个位置出现, 等价于 在 和 的最后出现.

• 若 在序列第 位出现, 则恒有 . 其中 为实验时前 个结果恰好是 的概率.

简单来说, 就是一旦出现了 , 立刻忘掉一切过去信息, 忘记出现过, 并且事件重新开始生成 (由于事件互相未必是独立的, 所以重新生成是有意义的).

定义如果序列最后四位恰好是 "hulu" 则称发生了事件, 那么可以看出这是一个 Recurrent Event. 这一步的关键在于字符串的最后一位 "u" 与 "h" 不同, 且 "lu" 与 "hu" 不同... 它的任何真后缀都不是自己的前缀, 这样的字符串天生就可以定义出 Recurrent Event.

那么假如字符串不满足这个条件呢? 假如我们等待的 pattern 是 "tencent", 那么把事件 定义为: "tencent" 在序列末尾, 且与序列中其他任何已被判定为事件出现的 "tencent" 都无 overlap. 这样定义出的事件又是满足 Recurrent Event 定义的了.

现在无论是正常的 hulu, 还是奇葩的 tencent, 我们都能把它的出现定义成一个 Recurrent Event 了, 于是现在问题就是, 如何求一个 Recurrent Event 首次出现的期望步数?

翻开下一页我就张大嘴了, 因为我看到了下面这个有趣的定理.

设 是 persistent, non-periodic 的 Recurrent Event, 是它在第 位发生的概率, 是首次发生所需次数的期望 (或称 waiting time), 则 特别地, 若 .

P. ErdösW. Feller

其中:

• persistent (常返) 指这个事件终会发生的概率为 1. (由于是 Recurrent Event, 那么也就会发生无穷次了)

• non-periodic (非周期) 指这个事件可能发生的所有位置的标号没有公因子. (反例: 1, -1 的序列上, "部分和为 0" 是一个 Recurrent Event, 但它只可能发生在偶数位置, 因此是 periodic 的)

这两个条件并不是十分强, 至少在我们的敲键盘游戏中它们显然都是满足的.

让我觉得神奇的不仅仅是这个定理的结论很牛 B, 还包括作者, 竟然是 Paul Erdös 与此书作者 Feller 合作的. (天才流浪者 Paul Erdös 大概算是我最喜欢的数学家了, 强烈推荐一本他的传记数字情种)

当即去找了这个定理的 paper, A property of power series with positive coefficients, paper 里给了这个定理在分析上的等价命题的两种证法, 其中一种还用了复变函数..

有了这个定理, 对于 Recurrent Event 的分析瞬间就一片光明了. 对于 hulu, 当时间足够长 (>3) 之后, 在时刻 出现这个 pattern 的概率恒为 , 于是发生事件的概率也是 , 那么 waiting time 自然是 .

而对于 tencent, 事件发生的概率不再是 了 (因为我们规定了不能 overlap, 所以不是单单出现了字符串就够的), 但是对于每个出现 "tencent" 的地方, 要么它自己结尾处事件出现, 要么它首位的 "t" 处事件出现, 因此可以列出如下递推式:

令 , 即可求出 , 取倒数便可得到期望等待时间.

类似的 pattern, 包括各个字符的出现概率不同什么的情况, 也就都可以算了. 可以去看看 Feller 的原书, 里面还有相关的很多结论, 比如生成函数啊之类的..

update: 统计之都曾经有过一篇文章, 给出了这一问题的更多解法, pdf 见这里