猴子打字

Random Process 课上提到一个很有趣的问题：Mean Time for Patterns. 假设 $X=(X_1,X_2,...)$ 是一串有序的 iid（独立且同分布，independent and identically distributed）离散随机变量。pdf（概率密度函数）已知，为 $p_i=P(X_j=i)$ 。如果我们对这串变量中的某一段特定排序的变量（称作模式 pattern）感兴趣，问题就是，如何计算出此 pattern 最早在变量串中出现的位置的期望。

这几乎让我立即想到（很无厘头的）无限猴子定理：“让一只猴子在打字机上随机地按键，当按键时间达到无穷时，几乎必然能够打出任何给定的文字，比如莎士比亚全集”。在这个定理里，猴子随机打出的字母就是 iid 离散随机变量，莎士比亚全集就是我们要寻找的 pattern。

Mean Time for Patterns 问题的计算需要分 pattern 是否为 overlapping 考虑，即是否存在 $k>0$ 使得 pattern 的前 $k$ 个子变量串与后 $k$ 个子变量串相等。overlapping 的情况计算略复杂，暂且这里假定莎士比亚全集不存在 overlapping。因为这里 overlapping 的定义只考虑首尾是否存在相同的串，对中间的相同串是不考虑的，所以这里还算合理的假设。

若 $T$ 为 pattern 第一次出现时，猴子的打字量，则 $E[T]=1/p$，where $p = p_{i_1} p_{i_2}\cdots p_{i_n}$. 其中 $p_{i_j} ~~ \forall j=1,\dots,n$ 为莎士比亚全集中第 $j$ 个字符被击打的概率。具体的推导还是挺有意思的，尤其是对 overlapping 情况的推导，相当奇淫。

这里再假设每个字符被击打的概率相等，键盘有 50 个键，则 $p_i=\frac{1}{50}$. 查到莎士比亚全集总共有 3,696,348 个字符。所以可以估算下这只倒霉猴子预期什么时候可以打出莎士比亚全集了。

$E[T]=\frac{1}{p}=\frac{1}{({\frac{1}{50}})^{3696348}}=50^{3696348}$ 这个值太大以至于计算机无法显示。

假设倒霉猴子每秒钟打两个字，那么一年的打字量就是 $2\times 3600\times 24 \times 365= 63072000$

打出整本莎士比亚全集需要的年数呢？令 $x=\frac{50^{3696348}}{63072000}$
等式两边同取自然对数 $ln(x) = 3696348 \times 3.9120 -17.9598=14460095.4162$
换以 10 为底的对数 $log_{10} (x) = \frac{14460095.4162}{ln(10)} \approx 6279940$

大约的意义就是打出莎士比亚全集平均需要猴子600 万年600 万位数字的年的时间。

说不定在这期间，猴子顺带也打出了 Facebook 全套代码什么的 _(:з」∠)_

向伟大 (可怜) 的猴子致敬！