无限猴子定理

无限猴子定理的表述如下：让一只猴子在打字机上随机地按键，当按键时间达到无穷时，几乎必然能够打出任何给定的文字，比如莎士比亚的全套著作。

一只黑猩猩随机地打字，只要时间足够，几乎必然可以打出法国国家图书馆中的每本书。

在这里，几乎必然是一个有特定含义的数学术语，“猴子”也不是一只真正意义上的猴子，它被用来比喻成一个可以产生无限随机字母序列的抽象设备。这个理论说明把一个很大但有限的数看成无限的推论是错误的。猴子精确地通过键盘敲打出一部完整的作品比如说莎士比亚的哈姆雷特，在宇宙的生命周期中发生的概率也是极其低的，但并不是零。

这个理论的变化形式包括多个甚至无限多个打字员，以及目标文本从一个完整的图书馆到一个简单的句子。这些表述可以追述到亚里士多德的《论产生和毁灭》和西塞罗的《论神之本性》，经过布莱兹·帕斯卡和乔纳森·斯威夫特，最后到现在的形象的打字员的表述形式。在20世纪早期，埃米尔·博雷尔和亚瑟·爱丁顿运用这个理论在统计力学基础中阐述隐式时间标尺。

起源

无限猴子定理是来自埃米尔·博雷尔一本1913年出版谈概率的书籍[1]，当中介绍了“打字的猴子”的概念。这个定理是概率论中的柯尔莫哥洛夫的零一律的其中一个命题的例子。不过，当波莱尔在书中提出零一律的这个特例时，柯尔莫哥洛夫的一般叙述并未给出（柯尔莫哥洛夫那本概率论的著作直到1933年才出版）。

定义

普遍认同的观点

关于此定理的叙述为：有无限只猴子用无限的时间会产生特定的文章。其实不必要出现了两件无限的事物，一只猴子打字无限次已经足够打出任何文章，而无限只猴子则能即时产生所有可能的文章。

其他定义

其他取代的叙述，可能是用大英博物馆或美国国会图书馆取代法国国家图书馆；另一个常见的版本是英语使用者常用的，就是猴子会打出莎士比亚的著作。

出处

这一典故的出处，乔纳森·斯威夫特1782年出版的的《格列佛游记》，第三部分第五章，教授要其学生通过经常转动机械把手产生一些随机的字句，以建立所有科学知识的列表。

证明

直接证明

两个独立事件同时发生的概率等于其中每个事件单独发生的概率的乘积。比如，在某一天台北下雨的可能性为0.3，旧金山地震的可能性是0.008（这两个事件可以视为相互独立的），那么它们同时发生的概率是0.3×0.008 = 0.0024。

假设一个打字机有50个键，想要打出的字是“banana”。随机的打字时，打出第一个字母“b”的概率是1/50，打出第二个字母“a”的概率也是1/50，因为事件是独立的，所以一开始就打出单词“banana”的概率是：

(1/50)×(1/50)×(1/50)×(1/50)×(1/50)×(1/50) =(1/50)6，

这个概率小于150亿分之1。同理，接下来继续打出“banana”的概率也是1/506。

所以，在给定的六个字母没有打出“banana”的概率是1−(1/50)6。因为每一段（6个字母）文字都是独立的，连续n段都没有打出“banana”的概率Xn是：

 

随着n变大，Xn在变小。当n等于100万时，Xn大约是0.9999（没有打出“banana”的概率是99.99%）；但是当n等于100亿时Xn大约是0.53（没有打出“banana”的概率是53%）；当n等于1000亿时Xn大约是0.0017（没有打出“banana”概率是0.17%）;当n趋于无穷时Xn趋于零。这就是说，只要使n足够大，Xn可以变得足够小。[注 1][2]

同样的论证也可以说明在无限多的猴子中有至少一个会打出一段特定的文章。这里Xn =(1−(1/50)6)n，其中Xn表示在前n个猴子中没有一个一次打出banana的概率。当我们有1000亿只猴子时，这个概率降低到0.17%，并且随着猴子数量n趋于无穷大，没有打出“banana”的概率Xn趋于0。

但是，在只有有限的时间和有限只猴子时，结论就大不一样了。如果我们的猴子数量和可观测宇宙中的基本粒子数量一样多，大约1080只，每秒钟打1000个字，持续打100倍于宇宙的生命长度的时间（大约1020秒）有猴子能够打出一本小书的概率也趋近于0。

无限长的字符串

以上两种情况可以扩展到所有的字符串：

  • 给定一个无限长的字符串，其中的每一个字符都是随机产生的，那么任意有限的字符串都会作为一个子字符串出现在其中（事实上要出现无限多次）。
  • 给定一个序列，其中有无限多个无限长的字符串，其中每一个字符串中的每一个字符都是随机产生的，那么任意有限的字符串都会出现在其中某些字符串的开头（事实上是无限多个字符串的开头）。

对于第二个定理，设Ek某给定字符串出现在第k个字符串开头的事件。有固定的且不为零的概率p是这个事件发生，而且Ek是独立的，所以：

 

事件Ek发生无穷多次的概率是1（波莱尔－坎泰利引理）。第一个定理可以类似地处理，先将无限长的字符串分割，使得每一段的长度和给定字符串相同，然后设Ek是第k段等于给定字符串的事件。[注 2]

概率

不算标点符号、空格、大小写，一个猴子随机打字打出的第一个字母和《哈姆雷特》中相同的概率是 ，前两个字母相同的概率是 （即 ）。因为概率发生了指数爆炸，前20个字母相同的概率是 。而打出的字和《哈姆雷特》的全部文本相同的概率降低到难以想象。整部《哈姆雷特》大约有130,000个字母[注 3] （页面存档备份，存于互联网档案馆）。虽然有3.4×10183,946分之一的概率一遍就正确地打出所有文本，在打出正确的文字之前平均需要输入的字母数量也要3.4×10183,946[注 4]，或者包括标点符号，4.4×10360,783[注 5]

即使可观测宇宙中充满了猴子一直不停地打字，能够打出一部《哈姆雷特》的概率仍然少于10183,800分之一[3]。

现实

实际在现实中，猴子打出一篇像样的文章的概率比理论上来的更加低。2003年，普利茅斯大学艺术媒体实验室课程的教师和学生使用2,000英镑津贴做了这个实验，结果打出了5张几乎全是‘S’的纸。最终打出的文字[4]没能成为一个完整的句子。[5]

程序员Jesse使用Hadoop、亚马逊EC2和Ubuntu，并以 ASCII 形式存在的随机数成功重现《莎士比亚全集》。[6]

相关条目

注释

  1. ^ 这表明在给定的六个字母中键入“香蕉”的可能性趋于1。
  2. ^ The first theorem is proven by a similar if more indirect route in Gut, Allan. Probability: A Graduate Course. Springer. 2005: 97–100. ISBN 0387228330. 
  3. ^ Using the Hamlet text from gutenberg, there are 132680 alphabetical letters and 199749 characters overall.
  4. ^ For any required string of 130,000 letters from the set a-z, the average number of letters that needs to be typed until the string appears is (rounded) 3.4 × 10183,946, except in the case that all letters of the required string are equal, in which case the value is about 4% more, 3.6 × 10183,946. In that case failure to have the correct string starting from a particular position reduces with about 4% the probability of a correct string starting from the next position（i.e., for overlapping positions the events of having the correct string are not independent; in this case there is a positive correlation between the two successes, so the chance of success after a failure is smaller than the chance of success in general）. The figure 3.4 × 10183,946 is derived from n = 26130000 by taking the logarithm of both sides: log10(n) = 1300000×log10(26) = 183946.5352, therefore n = 100.5352 × 10183946 = 3.429 × 10183946.
  5. ^ 26 letters ×2 for capitalisation, 12 for punctuation characters = 64, 199749×log10(64) = 4.4 × 10360,783.

参考文献

  1. ^ Émile Borel. Mécanique Statistique et Irréversibilité. J. Phys. (Paris). Series 5. 1913, 3: 189–196. 
  2. ^ Isaac, Richard E. The Pleasures of Probability. Springer. 1995: 48–50. ISBN 038794415X.  Isaac generalizes this argument immediately to variable text and alphabet size; the common main conclusion is on p. 50.
  3. ^ Kittel, Charles; Kroemer, Herbert. Thermal Physics 2nd. W. H. Freeman Company. 1980: 53. ISBN 0-7167-1088-9. 
  4. ^ Notes Towards the Complete Works of Shakespeare (PDF). [2019-04-02]. 原始内容存档于2013-01-20. 
  5. ^ No words to describe monkeys' play. [2017-08-01]. （原始内容存档于2019-01-21）. 
  6. ^ A Few More Million Amazonian Monkeys | Jesse Anderson. [2020-02-16]. （原始内容存档于2021-04-02） （美国英语）. 

外部链接