Infinite monkeys and Shakespeare

[chrisnhowell]

Does this thought experiment posit that BETWEEN the monkeys the complete works of Shakespeare can be compiled from individual words they type?

Or does it posit that ONE monkey, given infinite time, will produce an error-free complete works.

 

If it is the first scenario I can see this happening and I could actually imagine it working with just a large number of monkeys and a long time.

 

If it's the second scenario I have a problem. Not just that it is totally counter-intuitive or that infinite time is impossible to comprehend.

I realise that monkeys and typewriters are (fun) devices used to help think about complex theories pertaining to probabilities and infinity etc but I do have some serious questions:

Are the monkeys to be thought of as random letter generators?

If the experiment was posed as this - An infinite amount of monkeys, given infinite time could produce exactly the same sequence of randomly generated letters as another monkey had produced ( the same amount of characters as the complete works of Shakespeare) - I can understand that although this would be highly unlikely with a billion monkeys and a billion years, it WILL happen given infinity.

This is random letter generators producing a random sequence.

 

Shakespeare is not a random sequence.

I would argue that it is IMPOSSIBLE for a random letter generator to produce a work of non-random generated language of that length even given infinity.I accept that I don't know where the cut off point in length would be.

 

Why am I wrong? I assume that I am!

[Sensei]

Look at C/C++ source code:

for( int i = 'a'; i <= 'z'; i++ ) {
   for( int j = 'a'; j <= 'z'; j++ ) {
      for( int k = 'a'; k <= 'z'; k++ ) {
         if( ( i == 'c' ) && ( j == 'a' ) && ( k == 't' ) ) {
            printf( "cat!\n" );
            break;
         }
      }
   }
}

It goes through the all letters present in English alphabet and finds the all possible and impossible 3 letters English words. It requires just 26^3 = 17576 executions of internal for-loop to find the all combinations. The larger number of letters, obviously the more combinations, and harder to match the right one sequence.

In the above example, I stopped evaluation after finding "cat" word.

 

Edited March 3, 2019 by Sensei

[Strange]

17 minutes ago, chrisnhowell said:

Shakespeare is not a random sequence.

It is one possible random sequence.

Let's take an example sentence from Shakespeare: "To be or not to be." If you think that is somehow not a random sequence, that implies that if we have a machine that repeatedly generates random sequences of 18 characters, it would eventually generate all possible sequences except that one. Does that make sense to you?

 

[OldChemE]

I too agree that given sufficient time the works would be reproduced-- but there is no guarantee that the works would be produced in any finite time.  The catch is that, if the letters are being produced at random, multiple repetitions of previously produced patterns may occur.  In other words, this is different from a computer produce methodically working through all the permutations of letters.  Thus, we can posit that the works of Shakespeare will eventually be produced but we cannot know that it will occur within any arbitrarily large finite time.

[taeto]

The more exact way to say it might be: we cannot be sure that the works of Shakespeare will be produced in finite time, but at least the probability of them not being produced is zero.

The reason is that it is actually possible, however unlikely, that the monkey will punch an X every time, even if we assume that the monkey is perfectly randomized. The probability of this possibility is identically zero. It is similar if instead of the letter X you consider all strings of the same length as Shakespeare's works but not equal to Shakespeare's works.

Edited March 4, 2019 by taeto

[Strange]

It may also be important to note that the monkeys and typewriters are not meant to taken literally. I have seen at least one person argue against the concept on the basis that the monkeys would hammer at the keyboard with their fists, jam all the letters then get bored and go eat bananas. So the monkeys are purely a metaphor for random sequences such as these: https://www.random.org/sequences/

[Eric H]

10 hours ago, OldChemE said:

I too agree that given sufficient time the works would be reproduced--

Supposing the monkey completes the first page perfectly; then makes a mistake. How will it know to go back to the beginning and start again?

[Strange]

13 minutes ago, Eric H said:

Supposing the monkey completes the first page perfectly; then makes a mistake. How will it know to go back to the beginning and start again?

It won't. It will continue typing and the rest of the text might be perfect or it might diverge further from the original text.

But another monkey (or the same monkey, later) will type the first page perfectly, and then the second. Eventually, one of them will type the whole thing. (Again, remembering that these are Metaphorical Magic Monkeys.)

[Janus]

4 hours ago, Eric H said:

Supposing the monkey completes the first page perfectly; then makes a mistake. How will it know to go back to the beginning and start again?

As Strange has already pointed out, it won't.  But it doesn't have to in order for the basic premise to be true.

Let's replace the monkeys with a single coin that is tossed over and over again.  If it comes up heads, we'll consider this a 1, and tails is a 0.  starting with the first flip, each succession of 7 flips (8 if you want to include a parity bit.) represents the ASCII code for a character.   In an infinite series of coin flips,  you will find any finite series of "1"s and "0" somewhere,  Including a perfect ASCII version of the works of Shakespeare (along with  partially correct versions,  including every possible variation that is off by just a single 1 or 0, and a version where every 1 and 0 are inverted)

The fact that a huge number of incomplete or incorrect versions will be produced (like the version where every instance of the name "Hamlet" is replaced with "custard"), does not prevent the perfect version from eventually occurring.

 

[Eric H]

On ‎3‎/‎3‎/‎2019 at 5:03 PM, chrisnhowell said:

Does this thought experiment posit that BETWEEN the monkeys the complete works of Shakespeare can be compiled from individual words they type?

When you say the complete work of Shakespeare, do you mean all thirty seven plays plus all the poems and sonnets?

6 hours ago, Janus said:

Let's replace the monkeys with a single coin that is tossed over and over again.  If it comes up heads, we'll consider this a 1, and tails is a 0. 

Are you suggesting giving every letter of the alphabet a binary code of 0's and 1's? Would you give upper case letters a different binary code? The complete work of Shakespeare has a finite number of characters; how would you randomly stop coin flipping at the exact number of characters, after getting it word perfect?

6 hours ago, Janus said:

The fact that a huge number of incomplete or incorrect versions will be produced (like the version where every instance of the name "Hamlet" is replaced with "custard"), does not prevent the perfect version from eventually occurring.

If Hamlet is mentioned fifty times in the play, that would only make sense if custard was substituted fifty times. If Hamlet is given fifty different names, the plot will not make sense. Even if Hamlet is only called 'pxzlkw' five times, how will that make sense?  Random mistakes seem the more likely scenario.

[Janus]

55 minutes ago, Eric H said:

When you say the complete work of Shakespeare, do you mean all thirty seven plays plus all the poems and sonnets?

Sure, why not.

 

56 minutes ago, Eric H said:

Are you suggesting giving every letter of the alphabet a binary code of 0's and 1's? Would you give upper case letters a different binary code? The complete work of Shakespeare has a finite number of characters; how would you randomly stop coin flipping at the exact number of characters, after getting it word perfect?

A seven bit binary number has 128 possible different combinations of 1s and 0s, this is enough for all the upper case, lower case letter, all the numbers, and all the punctuation marks, with a few codes left over for special functions such as carriage return, end of page, start of text and end of text, etc. 

we are not talking about stopping randomly after some finite number of flips, we are talking about an infinite number of flips. Because the entire works of Shakespeare has a finite number of characters, the particular sequence of 1s and 0's that would be a perfect ASCII copy of them has to appear somewhere along an infinite series   of coin flips.

1 hour ago, Eric H said:

If Hamlet is mentioned fifty times in the play, that would only make sense if custard was substituted fifty times. If Hamlet is given fifty different names, the plot will not make sense. Even if Hamlet is only called 'pxzlkw' five times, how will that make sense?  Random mistakes seem the more likely scenario.

And your point is?  Sure random mistakes or long strings of complete gibberish will be more likely.  But that does not preclude every possible string of characters appearing somewhere in the infinitely long string, including the perfect copy and ones that are just slightly off.  The odds of flipping 1,000,000 heads in a row is pretty low,   The overwhelming number of consecutive 1,000,000 coin flips will contain both 1s and 0s,  But if you are allowed to keep flipping the coin long enough, eventually you will hit a stretch of 1,000,000 heads in a row.

[wtf]

I have a proof that any finite string will almost surely be generated by infinitely many monkeys typing forever.

First, we have to make precise the idea of infinitely many monkeys typing forever. If we regard striking a key (or randomly choosing a character) as a discrete event, it makes sense that a single monkey, typing forever, will generate a countably infinite string.

Now if we have countably infinite monkeys, they will generate countably many such countably infinite strings. Since a countable union of countable sets is countable, we gain no more strings than if there is just one monkey generating a countably infinite string.

Now the complete works of Shakespeare are certainly a finite string of symbols.

So the question comes down to this: What is the probability that a given countably infinite string contains every possible finite string as a substring somewhere in it?

Note that as long as our alphabet is finite, it makes no difference whether these are strings of alphabetic symbols, or just the symbols 0 and 1. 

A real number with the property that its decimal (or binary, same difference) expression contains every finite sequence at least once, is called disjunctive.

A sequence is called normal if it contains each finite sequence an asymptotically equal number of times. In other words as we go to infinity, each finite string occurs infinitely often.

It's clear that being normal is stronger than being disjunctive. And it's known that the measure of the normal numbers in the reals is 1.

This does not mean that ALL reals are normal; only that if you pick a random real, it will be normal with probability 1. There could be exceptions, in the same sense that the rationals have measure zero in the reals. A randomly chosen real is irrational with probability 1, yet the rationals still exist and you might get lucky and pick one. In the same way, it's possible that a randomly chosen real may not be normal, but the probability is zero. Remember that in infinitary probability, 0 doesn't mean impossible and 1 doesn't mean certain. We use the phrase "almost surely" to mean the probability is 1.

Since being normal implies being disjunctive, the probability of picking a random real that's disjunctive is also 1. However it's conceivable that we may be really unlucky and pick a measure zero event.

So with probability 1, a countably infinite string of letters of the English alphabet will contain every possible finite string; including the finite string that matches the complete works of Shakespeare.

There are sequences that might not contain the works of Shakespeare, but they're as rare as the rationals in the reals.

Note that it makes no difference whether you generate that infinite sequence with one monkey typing forever or countably many monkeys typing forever. It's the exact same thing. 

https://en.wikipedia.org/wiki/Disjunctive_sequence

https://en.wikipedia.org/wiki/Normal_sequence

 

Edited March 5, 2019 by wtf

[Eric H]

5 hours ago, Janus said:

A seven bit binary number has 128 possible different combinations of 1s and 0s, this is enough for all the upper case, lower case letter, all the numbers, and all the punctuation marks, with a few codes left over for special functions such as carriage return, end of page, start of text and end of text, etc. 

we are not talking about stopping randomly after some finite number of flips, we are talking about an infinite number of flips. Because the entire works of Shakespeare has a finite number of characters, the particular sequence of 1s and 0's that would be a perfect ASCII copy of them has to appear somewhere along an infinite series   of coin flips.

So if you converted the alphabet to a binary code, there are now a 128 possible different combinations to create the letter 'm'. I would suggest that if you converted the four lines of your quote above to a binary code, the odds of coin flipping to get it right would be astronomical. It would not be the easily achieved million to one odds.

 

29 minutes ago, wtf said:

Note that it makes no difference whether you generate that infinite sequence with one monkey typing forever or countably many monkeys typing forever. It's the exact same thing. 

It makes a difference to the monkeys, how are you going to encourage a monkey to bang away at a typewriter for its entire life?

 

33 minutes ago, wtf said:

it makes sense that a single monkey, typing forever, will generate a countably infinite string.

I am struggling to imagine a monkey that can live forever.

[Ghideon]

23 hours ago, Strange said:

It may also be important to note that the monkeys and typewriters are not meant to taken literally. I have seen at least one person argue against the concept on the basis that the monkeys would hammer at the keyboard with their fists, jam all the letters then get bored and go eat bananas.

Good point.
Slightly off topic/less serious: If someone persists in such a literal view, how about a counter argument along the following line? If infinite number of real monkeys are given infinite time, infinite number of typewriters (and infinite number bananas) then some monkeys, or descendants, will learn how to type and develop an interest in Shakespeare literature...

 

Edited March 5, 2019 by Ghideon
spelling

[Strange]

59 minutes ago, Eric H said:

So if you converted the alphabet to a binary code, there are now a 128 possible different combinations to create the letter 'm'.

You could use the ASCII code and you would find your chosen string somewhere in the infinite list of numbers. If you choose another encoding (EBCDIC or Unicode) you will find the string somewhere else in the infinite sequence.

I am surprised this seems like a difficult concept to grasp! (Just out of interest, do you think this somehow conflicts with your religious beliefs?)

59 minutes ago, Eric H said:

It makes a difference to the monkeys, how are you going to encourage a monkey to bang away at a typewriter for its entire life?

You do realise the monkeys are just metaphors?

[wtf]

1 hour ago, Eric H said:

 

how are you going to encourage a monkey to bang away at a typewriter for its entire life?

 

You're getting up and going to work tomorrow, aren't you?

Edited March 5, 2019 by wtf

[taeto]

1 hour ago, wtf said:

There are sequences that might not contain the works of Shakespeare, but they're as rare as the rationals in the reals.

In terms of probability, of course.

In terms of size (cardinality) there are vastly more sequences that do not contain, and also vastly more sequences that contain infinitely many, copies of the works of Shakespeare than there are rationals.

30 minutes ago, wtf said:

You're getting up and going to work tomorrow, aren't you?

Perhaps the monkey gets interested in Shakespeare after its retired.

I repeat a related question that I posted earlier, and to which I never figured out the answer.

Suppose you engage uncountably many monkeys for the follow-up project, which is to achieve a sequence which consists in infinite repetition of the works of Shakespeare, the next copy beginning immediately after the end of the previous one, and nothing else is allowed to appear. Is there some probability that at least one of the monkeys will achieve this, say if we assume that there are continuum many monkeys (one monkey for each real number)?

[Carrock]

An extract from a story I read years ago that stuck in my mind.

Readable ( but not easily ) at https://archive.org/stream/Fantastic_v20n02_1970-12/Fantastic_v20n02_1970-12_djvu.txt

 

Quote

 

So Michael made him a clock. It was a cube of dressed stone measuring a parsec on each edge.

“You don’t have to wind it, you don’t have to do a thing to it, Bosh,” Michael explained. “A small bird will come every millennium and sharpen its beak on this stone.

......

what Pithekos Pete had written was nearly, but not quite, the same thing:

‘From this session interdict

Every fowl of tyrant wingg,

Save the eaggle, feather’d kingg:

Dam machine the g is sticked.’

And if you never saw an angel cry, words cannot describe to you the show that Boshel put on then.

They are still at it tonight, typing away at random, for that last sad near-victory was less than a million billion cycles ago. And only a moment ago — half way back in the present cycle — one of the monkeys put together no less than nine Shakespearian words in a row.

There is still hope. And the bird has now worn the rock down to about half its bulk.

 

 

[taeto]

1 hour ago, Carrock said:

An extract from a story I read years ago that stuck in my mind.

Depending on the typing speed of an ever more practiced monkey, this might be close to accurate. I seem to remember typing about 120/min when we had typing class in school. Today's texting phenomena might achieve significantly higher or lower speeds.

As a side note, the bird's behavior is also, and more precisely, termed "feaking". The same word is used in slang for another common behavior, which I am not at liberty to elaborate on. It is not a worksafe item everywhere.

Anyway, I am getting curious about a ballpark figure for how far the bird would actually get with the rock before the first nine words get typed by a monkey working alone. It seems like a very nice type of applied question, as you have to consider the physical properties of the bird's beak and the brittleness and size of the rock.

English words seem to be about 5.5 characters long on average. So the monkey would have to punch about \(9\cdot 5.5+8 = 57.5\) characters right, when we include the blanks between words. If we allow for 64 keys on the typewriter, to accommodate lower and upper case letters as well as the necessary punctuation marks, then the monkey has a chance of one in \(64^{57.5} = 2^{345} \sim 7\cdot 10^{103}\) to make a hit on the first try. Given a solid typing speed, the monkey may achieve this once every \(6\cdot 10^{101}\) minutes, that is about once in \(10^{96}\) years. 

This is informative.But still leaves the question of how long we will have to wait until there is an actual hit. And how the bird is doing meanwhile with carving the rock.

Edited March 5, 2019 by taeto

[Strange]

28 minutes ago, Carrock said:

An extract from a story I read years ago that stuck in my mind.

Readable ( but not easily ) at https://archive.org/stream/Fantastic_v20n02_1970-12/Fantastic_v20n02_1970-12_djvu.txt

And that led me to this: https://what-if.xkcd.com/34/ which discusses the number of Tweets that are possible and how long it would take to read them all.

(Also a Dr Who episode, Heaven Sent)

[Janus]

7 hours ago, Eric H said:

So if you converted the alphabet to a binary code, there are now a 128 possible different combinations to create the letter 'm'. I would suggest that if you converted the four lines of your quote above to a binary code, the odds of coin flipping to get it right would be astronomical. It would not be the easily achieved million to one odds.

By a rough estimate, let's make it 10¹⁵⁶⁵ bits or flips.   So after this many flips, there would be a 1 in 10¹⁵⁶⁵ chance that I reproduced those lines in ASCII.  If I continue for another 10¹⁵⁶⁵ flips, I increase the chances that one of those two series is a prefect match. With each successive series of flips I further increase the chances of one of those series will be perfect match.  If I am allowed an unlimited number of series of flips, I am guaranteed to hit the perfect match eventually.

 

8 hours ago, Eric H said:

It makes a difference to the monkeys, how are you going to encourage a monkey to bang away at a typewriter for its entire life?

 

 

8 hours ago, Eric H said:

I am struggling to imagine a monkey that can live forever.

Both of these statements are examples of "not seeing the forest for the trees".

Nobody is suggesting that either of these methods of generating random sequences of infinite length are practical, and that you could actually assemble enough monkeys and have them bang away at typewriters long enough to produce said results, or flip a coin enough times to do so (The coin itself would disintegrate first).

These examples are just used as ways to visualize the generation of infinite random series.

It's like if I say that it would take just under 143 days to drive to the Moon at 70 mph.  This is just meant to illustrate the distance to the Moon in terms of everyday speeds.  To argue that you can't "drive" to the Moon, or that traveling to the Moon at a fixed speed of 70 mph is impractical, is missing the point.

[StringJunky]

If a monkey can type Shakespeare, given an infinite amount of time, does it make mathematical sense that an infinite number monkeys would type Shakespeare in an infinitesimal amount of time?  Or rather, as quickly as one monkey in that infinite number to type the minimum number of keys for the whole works.  Are the odds not 1?

Edited March 5, 2019 by StringJunky

[wtf]

51 minutes ago, StringJunky said:

If a monkey can type Shakespeare, given an infinite amount of time, does it make mathematical sense that an infinite number monkeys would type Shakespeare in an infinitesimal amount of time?  Or rather, as quickly as one monkey in that infinite number to type the minimum number of keys for the whole works.  Are the odds not 1?

Not at all. As I pointed out, one monkey generating a countably infinite sequence of letters is exactly equivalent to infinitely many monkeys doing the same. A countable union of countable sets is countable. 

[StringJunky]

28 minutes ago, wtf said:

Not at all. As I pointed out, one monkey generating a countably infinite sequence of letters is exactly equivalent to infinitely many monkeys doing the same. A countable union of countable sets is countable. 

OK.

[wtf]

11 hours ago, taeto said:

Suppose you engage uncountably many monkeys for the follow-up project, which is to achieve a sequence which consists in infinite repetition of the works of Shakespeare, the next copy beginning immediately after the end of the previous one, and nothing else is allowed to appear. Is there some probability that at least one of the monkeys will achieve this, say if we assume that there are continuum many monkeys (one monkey for each real number)?

The probability of choosing one particular real number at random from the set of real numbers in the unit interval (so that the total measure of the probability space is 1) is zero. As always that doesn't mean it can't happen ... just that the probability is zero.