Here’s Wikipedia on the Infinite Monkey Theorem. Do note, though, that what it actually says is that every infinite string of characters with each character chosen uniformly at random will almost surely contain every possible substring, including the integrality of Shakespeare’s works. An event that happens almost surely (the probability theoretic equivalent of measure theory’s almost everywhere) will happen with probability 1, but you cannot say for sure that it is what happens. For example, if I do the monkey and hit on my keyboard at random an infinite number of times, I could only hit the letter ‘a’. The probability of me doing this is 0, but it could happen.
Think about it. Shakespeare wrote many of the greatest plays of all time. What does it say that those same plays could independently be created by an unintelligent agent?
If the complete works of Shakespeare can be randomly generated after that famous author died, then a book could be randomly generated before an author is born.
Supposing that the existence of mankind is infinite, then we ought to invest all our computer resources in randomly generating text so that future man will never ever have to write another book again.
Well here’s an interesting thought. If you have an infinite string of characters created entirely at random it must, as you say, contain within it every possible configuration or substring.
One possible substring is the letter A strung together an infinite number of times. The liklihood of having a large number of As all in a row approaches zero the more we tack on to the string, but since no matter how small the probability is it is not equal to zero, then it must occur at some point as the entire string continues on towards infinity.
Given that, where on the string is there room for other characters if there’s already an infinite number of As?
I understand that there can actually be different levels of infinity. I just said it was an interesting thought.
No it must not. If I have an infinite string of characters, each of them chosen through an uniform distribution, and then choose a finite string of characters, I will find that it will appear as a substring in my infinite string with probability 1. But this doesn’t mean that it will actually appear. We are used to believe that an event that happens with probability 1 certainly occurs, but it isn’t true when dealing with infinite probability spaces.
You’re on the right track, but that’s not exactly it. If you take a finite string of characters (say of length n, and suppose for the sake of simplicity that the only possible characters are the lowercase letters), with each one chosen uniformly, the probability that your string will consist only of the letter ‘a’ is 1/26^n. But if you now take an infinite string of characters, the probability that it will consist of only the letter ‘a’ will be exactly 0. Again, that doesn’t mean that it is impossible, it only means that it will almost surely not occur.
I’m not a math guy, but isn’t it true that infinity is not a number, it is a concept? If so, then would it be accurate to simply say that as n increases it approches 0?
Infinity is indeed not a number (at least when working with standard definitions of the numbers). On the other hand, it is completely valid mathematically to work with an infinite string of characters. Such an object doesn’t exist in the real world, but in the mathematical world, there’s nothing contradictory about it. Yes, the probability that a finite string of length n will consist only of the letter ‘a’ (given the assumptions in my previous posts) will converge to 0 as n increases. But when working with an actual infinite string, the probability is exactly 0.
Why bother with all this randomness? Just program the computer to produce every possible byte, then every possible 2-byte stream, then every possible 3-byte stream, and so on.
If you leave it running long enough, it will eventually produce:
[ul]
[li]The text of every book or article that has ever been written, or ever will be written, which of course includes Shakespeare’s plays, every compilation of Shakespeare that was ever made, and every written work that quotes or refers to Shakespeare.[/li][li]Every movie that has ever been made, or ever will be made, in MPEG 1 and 2, DivX, QuickTime, and every other digital video format that ever has or will be invented.[/li][li]Every song that has ever been recorded, or ever will be recorded, in MP3, Ogg Vorbis, WMA, AAC (both with and without encryption for every person who ever has or ever will sign up for the iTunes Music Store), FLAC, WAV, and any other music format that ever has been or will be invented.[/li][li]A perfect image of every CD or DVD that has ever been made, in ISO, BIN/CUE, and NRG formats, along with cover art in JPEG, PNG, and any other image format that ever has been or will be invented.[/li][li]Every computer program, console game, and firmware that has ever been or will be made for every computer, game console, or embedded system.[/li][/ul]
Incidentally, this should make us carefully consider what it means when we talk about creating an intellectual work like a song or a program. Every track on a CD is just a very long number, and feeding that number into a CD player would produce the same sound whether or not a human being was ever around to work on it. All humans can do is speed up the process of finding the “right” numbers.
I think I saw it mentioned once, but if you have an infinite number of monkeys how do you monitor what they are producing? Well we have an answer for you.
The Infinite Monkey Protocol Suite (IMPS)
Yep someone took the time to come up with a scaleable protocol suite to manage the problem.
-Otanx
Is there any propositional logic behind this?
To clarify, I mean specifically the statement that, “when working with an actual infinite string, the probability is exactly 0”.
Here is a proof that if you have a uniform distribution over the set of all infinite strings of lowercase letters (or any set of characters), then the probability of choosing any one of them is exactly 0. It does require some basic knowledge of measure theory.
Note the set of all infinite strings of lowercase letters by S. S is an infinite set, indeed an uncountable set (easily proven with Cantor’s diagonal argument, see here or here). Consider a uniform distribution on S (that is, consider the act of choosing an element of S completely at random with each element having the same probability of appearing than any other one). Assume that the probability of an element of S appearing is not 0. Say it is equal to e > 0. Probabilities are countably additive, that is, if I take the union of a finite or countably infinite number of disjoint events, then its probability will be the sum of the probabilities of each event. Take any countably infinite subset of S, say T. The probability that we pick a string found in T will be equal to the sum over all elements of T of the probability that this particular element appears, that is, it will be equal to sum(e, n=1…infinity). But this equals infinity, which is a contradiction since the probability of choosing any string in S must be 1 and therefore the probability of choosing any string in T must be less than or equal to 1. Therefore, our assumption is incorrect: the probability of an element of S appearing must be equal to 0.
I think…maybe I get it. In a more straightforward way, suppose I had a uniformly distributed infinitely large deck of cards. The probability that I choose any card out of the deck is 1/infinity, which is infinitely small. From there, the concept of infinity provides that it is impossible that I will pick the card, as the deck is neverending.
It seems my problem arises in the knowledge that I will pick 1 card and therefore my odds must have been off by an infinitely small number. Which I guess is zero. (thanks for entertaining me thus far)
That one’s actually not straightforward at all. It’s possible to have a uniform distribution on a finite set, and it’s possible to have a uniform distribution on an uncountable set, but it’s not possible to have a uniform distribution on a countably infinite set.
If Pierre Menard could write the entire Quixote of Cervantes, word-for-word perfectly, then I suppose anything’s possible.
ok, forget that part…=)
In the words of the eminent Blair Houghton:
“Come to think of it, there are already a million monkeys on a million typewriters, and Usenet is NOTHING like Shakespeare.”
