写在前面：本文是作为概率论与数理统计的课程论文。
从众所周知的定理说开去…
想必大家在学习概率论的时候，都听过这样一个故事：一只猴子在打字机上随机敲击键盘，无限期地敲下去，最终会打出一部莎士比亚的作品。这个故事的出处[1]有许多说法，最初提出这个故事的人也不一定是英国人（那么提到的作品也大概不是莎士比亚的），这里不做细究。但是这个故事的意义却是显而易见的：在无限的时间里，一切都有可能发生。
这种一定发生的事情是多么的无聊。按照清华的传统，我们不妨把它变成一个比赛，排出一二三来。对猴子（学生）排序这件事，听起来有些恐怖。我们还是比一比哪部作品更容易被猴子写出来吧。我虽然读过莎翁的几篇著作，但是它们在我的榆木脑袋里并没有留下太多印象，而且不同作品的字数也不一样，显然不太公平。我们不妨比较一些字数相近的作品，中国古代的五言绝句就是一个很好的选择。我拍脑袋想到了《静夜思》和《八阵图》这两首诗，于是，我们的问题就是：一只猴子随机敲击键盘，更容易写出《静夜思》还是《八阵图》？
这个讨论真的有意义吗？
看到这里，很自然的一个想法是，两首诗长度相同，那么出现的概率自然也相同了。其实，问题没有这么简单。为了看清楚这一点，我们需要简化问题。键盘上的按键太多了，我们干脆让猴子抛硬币吧，这样我们得到的就是无限长的01序列（0代表正，1代表反），每个位置的结果独立，且0和1出现的概率相等。《静夜思》和《八阵图》这两首诗，我们暂且用011（正反反）和110（反反正）来表示，以便于猴子写出来。那么，这两个序列，哪一个先出现的概率高？
事实上，011首先出现的概率高达75%！虽然011和110的长度相同，出现的频率也是相同的，但是它们之间存在竞争（太可怕了）！011的第一个0出现的时候，110已经输了，因为它的第一个1还没有出现。在110的前缀11出现时，011就会取得胜利。因此，二者的胜率是3:1。
你说的对，所以怎么计算？
前置知识
为了更好地计算和理解，我们引入概率生成函数这一概念。它是一个形式幂级数，有些类似于唐老师上课讲的矩母函数。如果X是非负整数集N上的离散随机变量，那么X的概率生成函数为：
它有一些很好的性质。由于所有取值的概率之和为1，所以有：
对F（形式）求导，得到：
令，得到X的期望（这里不讨论它的存在性）：
使用一些技巧，可以得到X的方差：
所以，中蕴含了关于X的很多信息。关于生成函数，还有很多有趣的性质，这里暂且不表。
算法
我们考虑一个加强版的问题：给定个长度为
的01字符串，问每个字符串最先出现在随机01序列中的概率。
设表示字符串
在01序列的前
位中首次出现的概率，
表示在01序列的前
位中没有任何给定字符串出现的概率。它们对应的生成函数分别是
。回忆上一节的期望性质，我们要求的就是
。
我们可以得到怎样的等式关系？
根据定义，有，对应到生成函数：
带入，有：
好吧，有一些大炮打蚊子的感觉。这个等式的含义是，这个比赛一定会结束。
我们再来看看的递推关系，这里会体现竞争关系。我们用
表示第t个串的j前缀是否是i串的一个j后缀。那么，对于任意的
，有：
这个式子表示，在一个没有结束的序列之后补上串，就会得到一个结束的序列。但是这个序列可能在补完
串之前就已经结束了，所以我们要减去这部分。
带入，可以得到：
这给了我们个方程，再加上最开始的方程，我们就可以解出
这
个未知量，得到问题的答案。
计算机系的同学可能对时间复杂度比较感兴趣。这个算法的时间复杂度是（假设
同阶），瓶颈在于求
数组和解方程。另外，这个加强版的问题是信息学奥林匹克竞赛2017年的省队选拔题之一。
有趣的观察
至此，我们已经解决了这个问题的加强版。在结束之前，我还想分享一些有趣的观察。
对于只有两个字符串的情况，有一个相关的趣味游戏。在游戏中，A首先选择一个长度为n的01序列，然后B再选择另一个等长的01序列。哪位玩家的序列最先在抛硬币的结果序列中出现就获得胜利。这个游戏叫做Penney’s game，它是由 Walter Penney 在 1969 年提出来的[2]。
如果有朋友找你玩这个游戏，那么他可能是心怀鬼胎的。因为这个游戏总是对玩家B有利。更进一步的，如果把A选择的01串记为Sx，那么B选择0S或1S即可保证自己的胜率至少有。这里留作读者思考[3]。
揭晓答案
还记得本文开篇的问题吗？我们现在可以给出答案了！这里笔者自己充当了猴子，用输入法输入了这两首古诗并记录下敲击的键位，随后将它映射到长度为200的01序列。使用本文中的算法，可以得到这两首古诗的出现概率分别是——
0.5和0.5。事实上，计算机的浮点精度已经不能表示二者如此微小的差异了。这听起来有一些遗憾。于是我又尝试计算了猴子首先写出这两首古诗的题目的概率——0.4999980926和0.5000019074，《八阵图》更容易出现。嗯，很好，看来杜工部确实起标题比较随意啊。
参考文献
1 | [1] Infinite Monkey Theorem. (n.d.). Wikipedia. |