Editing Infinite monkey theorem (section)

==Solution==

===Direct proof===
There is a straightforward proof of this theorem. As an introduction, recall that if two events are [[statistically independent]], 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 [[Moscow]] on a particular day in the future is 0.4 and the chance of an [[earthquake]] in [[San Francisco]] on any particular day is 0.00003, then the chance of both happening on the same day is {{nowrap|1=0.4 × 0.00003 = 0.000012}}, [[Statistical assumption|assuming]] that they are indeed independent.

Consider the probability of typing the word ''banana'' on a typewriter with 50 keys. Suppose that the keys are pressed independently and uniformly at random, meaning that each key has an equal chance of being pressed regardless of what keys had been pressed previously. 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. Therefore, the probability of the first six letters spelling ''banana'' is:
:(1/50) × (1/50) × (1/50) × (1/50) × (1/50) × (1/50) = (1/50)<sup>6</sup> = 1/15,625,000,000.
The result is less than one in 15&nbsp;billion, but ''not'' zero.

From the above, the chance of ''not'' typing ''banana'' in a given block of 6 letters is 1&nbsp;−&nbsp;(1/50)<sup>6</sup>. Because each block is typed independently, the chance ''X''<sub>''n''</sub> of not typing ''banana'' in any of the first ''n'' blocks of 6 letters is:

:<math>X_n=\left(1-\frac{1}{50^6}\right)^n.</math>

As ''n'' grows, ''X''<sub>''n''</sub> gets smaller. For ''n'' = 1 million, ''X''<sub>''n''</sub> is roughly 0.9999, but for ''n'' = 10&nbsp;billion ''X''<sub>''n''</sub> is roughly 0.53 and for ''n'' = 100&nbsp;billion it is roughly 0.0017. As ''n'' approaches infinity, the probability ''X''<sub>''n''</sub> [[limit of a function|approaches]] zero; that is, by making ''n'' large enough, ''X''<sub>''n''</sub> can be made as small as is desired,<ref name="Isaac1995">{{cite book |last=Isaac |first=Richard E. |title=The Pleasures of Probability |publisher=Springer |year=1995 |isbn=0-387-94415-X |location=New York |pages=48–50 |oclc=610945749 |postscript=– Isaac generalizes this argument immediately to variable text and alphabet size; the common main conclusion is on page 50.}}</ref> and the chance of typing ''banana'' approaches 100%.{{efn|This shows that the probability of typing "banana" in one of the predefined non-overlapping blocks of six letters tends to 1. In addition the word may appear across two blocks, so the estimate given is conservative.}} Thus, the probability of the word ''banana'' appearing at some point in an infinite sequence of keystrokes is equal to one.

The same argument applies if we replace one monkey typing ''n'' consecutive blocks of text with ''n'' monkeys each typing one block (simultaneously and independently). In this case, ''X''<sub>''n''</sub> = (1&nbsp;−&nbsp;(1/50)<sup>6</sup>)<sup>''n''</sup> is the probability that none of the first ''n'' monkeys types ''banana'' correctly on their first try. Therefore, at least one of infinitely many monkeys will (''with probability equal to one'') produce a text using the same number of keystrokes as a perfectly accurate human typist copying it from the original.

====Infinite strings====
This can be stated more generally and compactly in terms of [[string (computer science)|strings]], which are sequences of characters chosen from some finite [[alphabet]]:
* Given an infinite string where each character is chosen independently and [[Uniform distribution (discrete)|uniformly at random]], any given finite string almost surely occurs as a [[substring]] at some position.
* Given an infinite sequence of infinite strings, where each character of each string is chosen independently and uniformly at random, any given finite string almost surely occurs as a prefix of one of these strings.

Both follow easily from the second [[Borel–Cantelli lemma]]. For the second theorem, let ''E''<sub>''k''</sub> be the [[event (probability theory)|event]] that the ''k''th string begins with the given text. Because this has some fixed nonzero probability ''p'' of occurring, the ''E''<sub>''k''</sub> are independent, and the below sum diverges,
:<math>\sum_{k=1}^\infty P(E_k) = \sum_{k=1}^\infty p = \infty,</math>
the probability that infinitely many of the ''E''<sub>''k''</sub> 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 ''E''<sub>''k''</sub> the event where the ''k''th block equals the desired string.{{efn|The first theorem is proven by a similar if more indirect route in Gut (2005).<ref>{{cite book |last=Gut |first=Allan |title=Probability: A Graduate Course |year=2005 |publisher=Springer |isbn=0-387-22833-0 |pages=97–100}}</ref>}}

===Probabilities===
However, for physically meaningful numbers of monkeys typing for physically meaningful lengths of time the results are reversed. If there were as many monkeys as there are atoms in the observable universe typing extremely fast for trillions of times the life of the universe, the probability of the monkeys replicating even a ''single page'' of Shakespeare is unfathomably small.

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&nbsp;×&nbsp;26) of typing the first two letters. Because the probability shrinks [[exponential growth|exponentially]], at 20&nbsp;letters it already has only a chance of one in 26<sup>20</sup> = 19,928,148,895,209,409,152,340,197,376{{efn|Nearly 20 octillion}} (almost 2&nbsp;×&nbsp;10<sup>28</sup>). In the case of the entire text of ''Hamlet'', the probabilities are so vanishingly small as to be inconceivable. The text of ''Hamlet'' contains approximately 130,000&nbsp;letters.{{efn|Using the Hamlet text {{cite web |url=http://www.gutenberg.org/dirs/etext99/1ws2611.txt |title=from gutenberg.org}}, there are 132680&nbsp;alphabetical letters and 199749 characters overall}} Thus, there is a probability of one in 3.4&nbsp;×&nbsp;10<sup>183,946</sup> 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&nbsp;×&nbsp;10<sup>183,946</sup>,{{efn|For any required string of 130,000&nbsp;letters from the set 'a'-'z', the average number of letters that needs to be typed until the string appears is (rounded) 3.4&nbsp;×&nbsp;10<sup>183,946</sup>, except in the case that all letters of the required string are equal, in which case the value is about 4% more, 3.6&nbsp;×&nbsp;10<sup>183,946</sup>. 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&nbsp;×&nbsp;10<sup>183,946</sup> is derived from ''n'' {{=}}&nbsp;26<sup>130000</sup> by taking the logarithm of both sides: log<sub>10</sub>(''n'') {{=}} 1300000×log<sub>10</sub>(26) {{=}}&nbsp;183946.5352, therefore ''n'' {{=}}&nbsp;10<sup>0.5352</sup>&nbsp;×&nbsp;10<sup>183946</sup> {{=}}&nbsp;3.429&nbsp;×&nbsp;10<sup>183946</sup>.}} or including punctuation, 4.4&nbsp;×&nbsp;10<sup>360,783</sup>.{{efn|26&nbsp;letters ×2 for capitalisation, 12 for punctuation characters {{=}} 64, 199749×log<sub>10</sub>(64) {{=}}&nbsp;4.4&nbsp;×&nbsp;10<sup>360,783</sup> (this is generous as it assumes capital letters are separate keys, as opposed to a key combination, which makes the problem vastly harder).}}

Even if every proton in the observable universe (which is [[Eddington number|estimated]] at roughly 10<sup>80</sup>) were a monkey with a typewriter, typing from the [[Big Bang]] until the [[end of the universe]] (when protons [[Proton decay|might no longer exist]]), they would still need a far greater amount of time – more than three hundred and sixty thousand ''orders of magnitude'' longer – to have even a 1 in 10<sup>500</sup> chance of success. To put it another way, for a one in a trillion chance of success, there would need to be 10<sup>360,641</sup> observable universes made of protonic monkeys.{{efn|There are ≈10<sup>80</sup>&nbsp;protons in the observable universe. Assume the monkeys write for 10<sup>38</sup> years (10<sup>20</sup>&nbsp;years is when [[Future of an expanding universe#Stellar remnants escape galaxies or fall into black holes|all stellar remnants will have either been ejected from their galaxies or fallen into black holes]], 10<sup>38</sup> years is when all but 0.1% of [[Future of an expanding universe#All nucleons decay|protons have decayed]]). Assuming the monkeys type non-stop at a ridiculous 400&nbsp;[[words per minute]] (the world record is 216&nbsp;[[words per minute|WPM]] for a single minute), that is about 2,000&nbsp;characters per minute (Shakespeare's average word length is a bit under 5&nbsp;letters). There are about half a million minutes in a year, this means each monkey types half a billion characters per year. This gives a total of 10{{sup|80}}×10{{sup|38}}×10{{sup|9}} {{=}} 10{{sup|127}} letters typed – which is still zero in comparison to 10{{sup|360,783}}. For a one in a trillion chance, multiply the letters typed by a trillion: 10<sup>127</sup>×10<sup>15</sup> {{=}} 10<sup>145</sup>. 10<sup>360,783</sup>/10<sup>145</sup> {{=}} 10<sup>360,641</sup>.}} As [[Charles Kittel|Kittel]] and [[Herbert Kroemer|Kroemer]] put it in their textbook on [[thermodynamics]], the field whose statistical foundations motivated the first known expositions of typing monkeys,<ref name="KK">{{cite book |last1=Kittel |first1=Charles |title=Thermal Physics |last2=Kroemer |first2=Herbert |publisher=W.H. Freeman Company |year=1980 |isbn=0-7167-1088-9 |edition=2nd |location=San Francisco |page=53 |oclc=5171399 |author1-link=Charles Kittel |author2-link=Herbert Kroemer}}</ref> "The probability of ''Hamlet'' is therefore zero in any operational sense of an event&nbsp;...", and the statement that the monkeys must eventually succeed "gives a misleading conclusion about very, very large numbers."

In fact, there is less than a one in a trillion chance of success that such a universe made of monkeys could type any particular document a mere 79&nbsp;characters long.{{efn|As explained at {{cite web |url=http://www.nutters.org/docs/more-monkeys |title=More monkeys |access-date=2013-12-04 |url-status=dead |archive-url=https://web.archive.org/web/20150418004018/https://www.nutters.org/docs/more-monkeys |archive-date=2015-04-18 |df=dmy-all}} The problem can be approximated further: 10<sup>145</sup>/log<sub>10</sub>(64) {{=}}&nbsp;78.9 characters.}}

An online demonstration showed that short random programs can produce highly structured outputs more often than classical probability suggests, aligning with [[Gregory Chaitin]]'s modern theorem and building on [[Algorithmic Information Theory]] and [[Algorithmic probability]] by [[Ray Solomonoff]] and [[Leonid Levin]].<ref name="ZenilSolerToscano2013">{{cite web|title=Infinite Monkey Theorem |url=https://demonstrations.wolfram.com/InfiniteMonkeyTheorem/ |website=Wolfram Demonstrations Project |author=Zenil, Hector and Soler-Toscano, Fernando |date=October 2013 |access-date=May 24, 2024}}</ref> The demonstration illustrates that the chance of producing a specific binary sequence is not shorter than the base-2 logarithm of the sequence length, showing the difference between [[Algorithmic probability]] and [[classical probability]], as well as between random programs and random letters or digits.

===Almost surely===
{{Main|Almost surely}}
{{Unreferenced section|date=May 2024}}

The probability that an infinite randomly generated string of text will contain a particular finite substring is&nbsp;1. However, this does not mean the substring's absence is "impossible", despite the absence having a prior probability of 0. For example, the immortal monkey ''could'' randomly type G as its first letter, G as its second, and G as every single letter, thereafter, producing an infinite string of Gs; at no point must the monkey be "compelled" to type anything else. (To assume otherwise implies the [[gambler's fallacy]].) However long a randomly generated finite string is, there is a small but nonzero chance that it will turn out to consist of the same character repeated throughout; this chance approaches zero as the string's length approaches infinity. There is nothing special about such a monotonous sequence except that it is easy to describe; the same fact applies to any nameable specific sequence, such as "RGRGRG" repeated forever, or "a-b-aa-bb-aaa-bbb-...", or "Three, Six, Nine, Twelve…".

If the hypothetical monkey has a typewriter with 90 equally likely keys that include numerals and punctuation, then the first typed keys might be "3.14" (the first three [[digits of pi]]) with a probability of (1/90)<sup>4</sup>, which is 1/65,610,000. Equally probable is any other string of four characters allowed by the typewriter, such as "GGGG", "mATh", or "q%8e". The probability that 100 randomly typed keys will consist of the first 99 digits of pi (including the separator key), or any other ''particular'' sequence of that length, is much lower: (1/90)<sup>100</sup>. If the monkey's allotted length of text is infinite, the chance of typing only the digit of pi is 0, which is just as ''possible'' (mathematically probable) as typing nothing but Gs (also probability 0).

The same applies to the event of typing a particular version of ''Hamlet'' followed by endless copies of itself; or ''Hamlet'' immediately followed by all the digits of pi; these specific strings are [[infinite set|equally infinite]] in length, they are not prohibited by the terms of the thought problem, and they each have a prior probability of 0. In fact, ''any'' particular infinite sequence the immortal monkey types will have had a prior probability of 0, even though the monkey must type something.

This is an extension of the principle that a finite string of random text has a lower and lower probability of ''being'' a particular string the longer it is (though all specific strings are equally unlikely). This probability approaches 0 as the string approaches infinity. Thus, the probability of the monkey typing an endlessly long string, such as all of the digits of pi in order, on a 90-key keyboard is (1/90)<sup>∞</sup> which equals (1/∞) which is essentially 0. At the same time, the probability that the sequence ''contains'' a particular subsequence (such as the word MONKEY, or the 12th through 999th digits of pi, or a version of the King James Bible) increases as the total string increases. This probability approaches 1 as the total string approaches infinity, and thus the original theorem is correct.

===Correspondence between strings and numbers===
In a simplification of the thought experiment, the monkey could have a typewriter with just two keys: 1 and 0. The infinitely long string thusly produced would correspond to the [[Binary numeral system|binary]] digits of a particular [[real number]] between 0 and 1. A countably infinite set of possible strings end in infinite repetitions, which means the corresponding real number is [[rational number|rational]]. Examples include the strings corresponding to one-third (010101...), five-sixths (11010101...) and five-eighths (1010000...).  Only a subset of such real number strings (albeit a countably infinite subset) contains the entirety of ''Hamlet'' (assuming that the text is subjected to a numerical encoding, such as [[ASCII]]).

Meanwhile, there is an ''[[uncountably]]'' infinite set of strings that do not end in such repetition; these correspond to the [[irrational numbers]]. These can be sorted into two uncountably infinite subsets: those that contain ''Hamlet'' and those that do not. However, the "largest" subset of all the real numbers is that which not only contains ''Hamlet'', but that also contains every other possible string of any length, and with equal distribution of such strings. These irrational numbers are called [[normal number|normal]]. Because almost all numbers are normal, almost all possible strings contain all possible finite substrings. Hence, the probability of the monkey typing a normal number is 1. The same principles apply regardless of the number of keys from which the monkey can choose; a 90-key keyboard can be seen as a generator of numbers written in base 90.