I was just wondering, does the infinite monkey theorem also has a proof? And why is this called a theorem? It is sheer common sense. And what are its applications. I have heard about PHP and IEP and I also know that they are pretty useful. But what is the use of this and what is its proof?
$\begingroup$
$\endgroup$
1
asked Apr 24, 2015 at 9:03
-
2$\begingroup$ A theorem does not need to be profound. It's also true that a number of things that are sheer common sense turn out to be false (especially, though not only, in mathematics). $\endgroup$– Brian TungCommented Apr 24, 2015 at 17:06
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
9
The infinite monkey theorem states that if you have an infinite number of monkeys each hitting keys at random on typewriter keyboards then, with probability 1, one of them will type the complete works of William Shakespeare.
Let $A_n$ be the event that the $n^{th}$ monkey types the complete works of Shakespeare. Then if there are $m$ characters on the keyboard and $N$ characters in the complete works of Shakespeare, $\mathsf{P}(A_n) = m^{-N}$ for each $n$. Furthermore the $A_n$ are mutually independent. Hence, by the second Borel-Cantelli Lemma, since $$\sum_{n=1}^{\infty} \mathsf{P}(A_n) = \sum_{n=1}^{\infty} m^{-N} = \infty,$$ infinitely many of the events $A_n$ occur i.e. infinitely many monkeys will type the complete works of Shakespeare.
answered Apr 24, 2015 at 9:04
-
$\begingroup$ Thanks! But can you give me an even simpler proof? Without the use of other complex theorems? And how can the theorem say that the monkey can definitely type the works? And if infinite time is given, then any event can occur with probability 1. I am not exactly questioning the theorem, but can you please clear the doubt? $\endgroup$ Commented Apr 24, 2015 at 9:07
-
$\begingroup$ @Tomek: This seems to be confusing: if they type for an unlimited time, then you only need one monkey. The probability $m^{-N}$ seems to refer to the event that a monkey writes the given work "at the beginning". Also, in your conclusion, I miss some kind of "with probability 1" statement or so. Last but not least, isn't that Canetelli Lemma an overkill? $\endgroup$ Commented Apr 24, 2015 at 9:53
-
$\begingroup$ @AdityaAgarwal it is a theorem about a probability hence probabilty theory is the tool to use. Also, Borel-Cantelli is more or less equivalent to the infinite monkey theorem. The idea is to compare convergence of $1-\prod(1-p)$ with that of $\sum p$ $\endgroup$ Commented Apr 24, 2015 at 9:55
-
$\begingroup$ I still dont get the point. Can you prove the theorem without any complex lemma or theorem, justby pure math or as you said-probability theory? $\endgroup$ Commented Apr 24, 2015 at 9:57
-
1$\begingroup$ @Aditya: If you prefer, more intuitively, you can complete the demonstration as follows: One monkey fails to type the CWOS (from the beginning) with probability $1-1/m^N$. Two monkeys fail to type it with probability $(1-1/m^N)^2$. In general, $k$ monkeys fail to type it with probability $(1-1/m^N)^k$. Since $1-1/m^N < 1$, you can always set $k$ arbitrarily large to make the probability of failure arbitrarily small. Thus, out of an infinite number of monkeys, at least one (in fact, an infinite number) will succeed in typing CWOS. $\endgroup$ Commented Apr 24, 2015 at 17:00