The Infinite Monkey Theorem – 无限猴子定理
Infinite monkey’s writing Shakespeare 猴子可以打出“莎士比亚”作品
无限猴子定理的表述如下：让一只猴子在打字机上随机地按键，当按键时间达到无穷时，必然能够打出任何给定的文字，比如莎士比亚的全套著作。
一只黑猩猩随机地打字，只要时间足够，必然可以打出法国国家图书馆中的每本书。
Given enough time, a hypothetical chimpanzee typing at random would, as part of its output, almost surely produce one of Shakespeare’s plays.
Infinite monkey theorem
The infinite monkey theorem states that a monkey hitting keys at random on a typewriter keyboard for an infinite amount of time will almost surely type a given text, such as the complete works of William Shakespeare.
In this context, “almost surely” is a mathematical term with a precise meaning, and the “monkey” is not an actual monkey, but a metaphor for an abstract device that produces a random sequence of letters ad infinitum. The theorem illustrates the perils of reasoning about infinity by imagining a vast but finite number, and vice versa. The probability of a monkey exactly typing a complete work such as Shakespeare’s Hamlet is so tiny that the chance of it occurring during a period of time of the order of the age of the universe is minuscule, but not zero.
Variants of the theorem include multiple and even infinitely many typists, and the target text varies between an entire library and a single sentence. The history of these statements can be traced back to Aristotle’s On Generation and Corruption and Cicero’s De natura deorum, through Blaise Pascal and Jonathan Swift, and finally to modern statements with their iconic typewriters. In the early 20th century, émile Borel and Arthur Eddington used the theorem to illustrate the timescales implicit in the foundations of statistical mechanics. Various Christian apologists on the one hand, and Richard Dawkins on the other, have argued about the appropriateness of the monkeys as a metaphor for evolution.
Popular interest in the typing monkeys is sustained by numerous appearances in literature, television, radio, music, and the Internet. In 2003, an experiment was performed with six Celebes Crested Macaques, but their literary contribution was five pages consisting largely of the letter ‘S’.
==================================================================
Direct proof
There is a straightforward proof of this theorem. If two events are statistically independent, (i.e. neither affects the outcome of the other), then the probability of both happening equals the product of the probabilities of each one happening independently. For example, if the chance of rain in Sydney on a particular day is 0.3 and the chance of an earthquake in San Francisco on that day is 0.008 (reasonably assumed to be independent events), then the chance of both happening on that same day is 0.3 × 0.008 = 0.0024.
Suppose the typewriter has 50 keys, and the word to be typed is ‘banana’. Typing at random, the chance that the first letter typed is ‘b’ is 1/50, and the chance that the second letter typed is a is also 1/50, and so on, because events are independent. Therefore, the chance of the first six letters matching banana is
(1/50) × (1/50) × (1/50) × (1/50) × (1/50) × (1/50) = (1/50)6,
less than one in 15 billion. For the same reason, the chance that the next 6 letters match banana is also (1/50)6, and so on.
From the above, the chance of not typing banana in a given block of 6 letters is 1 ? (1/50)6. Because each block is typed independently, the chance Xn of not typing banana in any of the first n blocks of 6 letters is
X_n=\left(1-\frac{1}{50^6}\right)^n.
As n grows, Xn gets smaller. For an n of a million, Xn is roughly 0.9999 (i.e. the chance of not typing banana is roughly 99.99%), but for an n of 10 billion Xn is roughly 0.53 (i.e. the chance of not typing banana is roughly 53%) and for an n of 100 billion it is roughly 0.0017 (i.e. the chance of not typing banana is roughly 0.17%). As n approaches infinity, the probability Xn approaches zero; that is, by making n large enough, Xn can be made as small as is desired, and the chance of typing banana approaches 100%.
The same argument shows why at least one of infinitely many monkeys will (almost surely) produce a text as quickly as it would be produced by a perfectly accurate human typist copying it from the original. In this case Xn = (1 ? (1/50)6)n where Xn represents the probability that none of the first n monkeys types banana correctly on their first try. When we consider 100 billion monkeys, the probability falls to 0.17%, and as the number of monkeys n increases, the value of Xn – the probability of the monkeys failing to reproduce the given text – approaches zero arbitrarily closely. The limit, for n going to infinity, is zero.
However, for physically meaningful numbers of monkeys typing for physically meaningful lengths of time (rather than infinities) the results are reversed. If there are as many monkeys as there are particles in the observable universe (1080), and each types 1000 keystrokes per second for 100 times the life of the universe (1020 seconds), the probability of the monkeys replicating even a short book approaches zero. See Probabilities, below.
Infinite strings
The two statements above can be stated more generally and compactly in terms of strings, which are sequences of characters chosen from some finite alphabet:
* Given an infinite string where each character is chosen uniformly at random, any given finite string almost surely occurs as a substring at some position (and indeed, infinitely many positions).
* Given an infinite sequence of infinite strings, where each character of each string is chosen uniformly at random, any given finite string almost surely occurs as a prefix of one of these strings (and indeed, as a prefix of infinitely many of these strings in the sequence).
Both follow easily from the second Borel–Cantelli lemma. For the second theorem, let Ek be the event that the kth string begins with the given text. Because this has some fixed nonzero probability p of occurring, the Ek are independent, and the below sum diverges,
\sum_{i=1}^\infty P(E_k) = \sum_{i=1}^\infty p = \infty,
the probability that infinitely many of the Ek occur is 1. The first theorem is shown similarly; one can divide the random string into nonoverlapping blocks matching the size of the desired text, and make Ek the event where the kth block equals the desired string.
Probabilities
Ignoring punctuation, spacing, and capitalization, a monkey typing letters uniformly at random has a chance of one in 26 of correctly typing the first letter of Hamlet. It has a chance of one in 676 (26 × 26) of typing the first two letters. Because the probability shrinks exponentially, at 20 letters it already has only a chance of one in 2620 = 19,928,148,895,209,409,152,340,197,376 (almost 2 × 1028). In the case of the entire text of Hamlet, the probabilities are so vanishingly small they can barely be conceived in human terms. The text of Hamlet contains approximately 130,000 letters. Thus there is a probability of one in 3.4 × 10183,946 to get the text right at the first trial. The average number of letters that needs to be typed until the text appears is also 3.4 × 10183,946, or including punctuation, 4.4 × 10360,783.
Even if the observable universe were filled with monkeys typing for all time, their total probability to produce a single instance of Hamlet would still be less than one in 10183,800. As Kittel and Kroemer put it, “The probability of Hamlet is therefore zero in any operational sense of an event…”, and the statement that the monkeys must eventually succeed “gives a misleading conclusion about very, very large numbers.” This is from their textbook on thermodynamics, the field whose statistical foundations motivated the first known expositions of typing monkeys.
original link
http://en.wikipedia.org/wiki/Infinite_monkey_theorem
无限猴子定理
无限猴子定理的表述如下：让一只猴子在打字机上随机地按键，当按键时间达到无穷时，必然能够打出任何给定的文字，比如莎士比亚的全套著作。
一只黑猩猩随机地打字，只要时间足够，必然可以打出法国国家图书馆中的每本书。
起源
无限猴子定理是来自埃米尔·博雷尔一本1909年出版谈概率的书籍，当中介绍了“打字的猴子”的概念。这个定理是概率论中的柯尔莫哥洛夫的零一律的其中一个命题的例子。不过，当波莱尔在书中提出零一律的这个特例时，柯尔莫哥洛夫的一般叙述并未给出（柯尔莫哥洛夫那本概率论的著作直到1933年才出版）。
普遍认同的观点
关于此定理的叙述为：有无限只猴子用无限的时间会产生特定的文章。其实不必要出现了两件无限的事物，一只猴子打字无限次已经足够打出任何文章，而无限只猴子则能即时产生所有可能的文章。
其他定义
其他取代的叙述，可能是用大英博物馆或美国国会图书馆取代法国国家图书馆；另一个常见的版本是英语使用者常用的，就是猴子会打出莎士比亚的著作。
直接证明
两个独立事件同时发生的概率等于其中每个事件单独发生的概率的乘积。比如，在某一天悉尼下雨的可能性为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/50)6。
所以，在给定的六个字母没有打出“banana”的概率是1 ? (1/50)6。因为每一段（6个字母）文字都是独立的，连续n段都没有打出“banana”的概率Xn是：
X_n=\left(1-\frac{1}{50^6}\right)^n\,
随着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是独立的，所以：
\sum_{i=1}^\infty P(E_k) = \sum_{i=1}^\infty p = \infty,
事件Ek发生无穷多次的概率是1。第一个定理可以类似地处理，先将无限长的字符串分割，使得每一段的长度和给定字符串相同，然后设Ek是第k段等于给定字符串的事件。
概率
不算标点符号、空格、大小写，一个猴子随机打字打出的第一个字母和哈姆雷特中相同的概率是1/26，前两个字母相同的概率是1/676（26 × 26）。因为概率发生了指数爆炸，前20个字母相同的概率是1/2620 = 19,928,148,895,209,409,152,340,197,376（大约2×1028）。而打出的字和哈姆雷特中的全部文本相同的概率降低到超出人们的想象。整部哈姆雷特大约有130,000个字母。[4] 虽然有3.4×10183,946分之一的概率一遍就正确地打出所有文本，在打出正确的文字之前平均需要输入的字母数量也要3.4×10183,946，[5]或者包括标点符号，4.4×10360,783。
即使可观测宇宙中充满了猴子一直不停地打字，能够打出一部哈姆雷特的概率仍然少于10183,800分之一。
original link
http://zh.wikipedia.org/wiki/%E7%84%A1%E9%99%90%E7%8C%B4%E5%AD%90%E5%AE%9A%E7%90%86
————————————————————–
http://www.sparkyblue.org
http://www.sparkyblue.com
http://www.simonsu.com
————————————————————–
October 20th, 2009 
admin 
