Jump to content
chrisnhowell

Infinite monkeys and Shakespeare

Recommended Posts

1 hour ago, taeto said:

You cut away the context yet again, so here is the paragraph you seem to be replying to, judging from the time stamp:

"if you have infinitely many monkeys, each hammering away randomly on a (their own individual) keyboard, and each continuing forever without stopping, then it might be interesting to observe whether any of them might fail to reproduce the works of Shakespeare infinitely many times. We already know that a single monkey will make it with 100% probability. The question is whether any of the monkeys might fail to achieve this, now that there are so many of them. And more precisely, what is the probability that at least one monkey fails, or even, what is the expected number of failure monkeys?"

1) There was no n or S given in the question, so I do not know what the quantities refer to. But I suspect that it means that you are supposed to count every occurrence of when a sequence of n letters matches exactly to the works of Shakespeare, assuming that the combined works of Shakespeare amount to precisely n letters. So yes, that is the idea.

2) No, you would not do that. You would take every sequence of the suitable length n and compare it to Shakespeare.

3) Yes.

4) No.

What is the bearing of this on what will happen when you engage a crew of infinitely many monkeys? Unless I am missing something, we already know that the works of Shakespeare will appear with probability 1 infinitely many times in the output of the typings of a single monkey.

Sorry if there was insufficient context, I though I was being economical with expression, like a Mathematician.

:)

However your responses are a bit puzzling here.

They are usually spot on.

You introduced n, not I. And n is not a count of every occurrence when a sequence of n letters (there you used it differently yourself) "matches the works of Shakesspeare."

n is count of the letters produced to date by a given  monkey, in whatever sequence they arrive.
I am tacitly assuming the monkey only types one letter at a time, or they could not appear in sequence.

A few posts back, I did define S as the exact count of letters in the works of Shakespeare, so that we could all use it for short.

Quote

You would take every sequence of the suitable length n and compare it to Shakespeare.

Here you are using n to stand for something different again and I'm sorry to say, using it wrongly.

Remember that the letters come one at a time and form a continual stream of growing length, n.
This also makes a fixed unalterable (growing) sequence.

They do not form multiple suitable or unsuitable sequences. That requires partitioning the stream (or partitioning the theoretical set of all the letters ever produced by that particular monkey)

Quote

You cut away the context yet again, so here is the paragraph you seem to be replying to, judging from the time stamp:

Actually I thought I included the paragraph I replied to which is not the one you quote.

 

Quote

Studiot

6 hours ago, taeto said:

Assume that each of a countably infinite crew of monkeys is assigned with the task to type random letters without ever stopping. What is the probability of the event that each monkey returns infinitely many copies of the complete manuscript to the works of Shakespeare?

None of us are being entirely rigorous here.

The answer to the above depends upon how you partition the output set.

However it is your paragraph that accurately describes the expanding stream of  n letters produced by any particular monkey.

Share this post


Link to post
Share on other sites
Posted (edited)
11 hours ago, taeto said:

 

Yes, a single monkey will type the works of Shakespeare on repeat with probability zero. Because the single monkey will be restricted to type a single sequence of letters, whereas there is continuum many possible sequences to choose from. 

But that was not the question. The question was what happens if you engage not a single monkey, but continuum infinitely many. The number of monkeys will be the same as the number of possible sequences. You expect that the expected number of monkeys to achieve the correct sequence will be equal to 1, no?

> Yes, a single monkey will type the works of Shakespeare on repeat with probability zero. Because the single monkey will be restricted to type a single sequence of letters, whereas there is continuum many possible sequences to choose from.

No, the probability is 1. I already explained that.. Remember the key fact is that the CWS is a finite string of symbols. It's exactly the same question as asking whether a random real number is disjunctive. It is, with probability 1. As well as normal with probability 1. So a random countably infinite strings of characters from the English alphabet contains the CWS infinitely many times with probability 1.

> But that was not the question. The question was what happens if you engage not a single monkey, but continuum infinitely many. The number of monkeys will be the same as the number of possible sequences. You expect that the expected number of monkeys to achieve the correct sequence will be equal to 1, no?

I'd expect the number of monkeys to type the CWS to be an uncountable infinity. That's because the chance of each one doing so is 1, as we've already seen. And now there are uncountably many monkeys. Almost all of them will type the CWS.

If I'm misunderstanding your question please let me know. 

 

Edited by wtf

Share this post


Link to post
Share on other sites
Posted (edited)
19 hours ago, studiot said:

 

So one monkey, typing an infinite amount of characters, would not only type out the complete works of Shakespeare,
She would also type out all the (infinite) characters of Pi. Remember the sequence of Pi never repeats.

 

No that's not true. The key to the CWS is that the complete works of Shakespeare is a FINITE sequence of symbols. And we know that almost all real numbers are normal, hence disjunctive. So with probability 1, a random countably infinite string not only contains the CWS, but contains the CWS infinitely many times.

But now you are asking about an INFINITE string. Why should some random infinite string contain every INFINITE string? And where would such a string appear? Remember the string is contiguous as in the digits of a real number. You can't have the digits of pi appearing as a substring in the middle. It would have to be a tail of the sequence. Your analysis isn't correct here.

Edited by wtf

Share this post


Link to post
Share on other sites
4 hours ago, wtf said:

No that's not true. The key to the CWS is that the complete works of Shakespeare is a FINITE sequence of symbols. And we know that almost all real numbers are normal, hence disjunctive. So with probability 1, a random countably infinite string not only contains the CWS, but contains the CWS infinitely many times.

But now you are asking about an INFINITE string. Why should some random infinite string contain every INFINITE string? And where would such a string appear? Remember the string is contiguous as in the digits of a real number. You can't have the digits of pi appearing as a substring in the middle. It would have to be a tail of the sequence. Your analysis isn't correct here.

I'm sorry there are incorrect statements in your postings in  this thread.

A Continuum

Def:- A compact connected set.

The integers are not connected.

The monkeys never type 0.5 characters or 10.378 characters.

 

One of the great achievements of Cantor was to remove the need to worry about potential v actual infinities.

He pointed out that it doesn't matter that you can't practically go on typing forever.

But you can specify a set which contains the entire output of such an infinite process.

I have been considering such a set in this case.

 

So consider the monkey typing away forever and consider the set which holds that output.

 

What do you consider the cardinality of that set to be?

 

The answer to this is the basis for my answer to your other questions to me.

 

8 hours ago, wtf said:

I'd expect the number of monkeys to type the CWS to be an uncountable infinity.

 

How can this be?

Share this post


Link to post
Share on other sites
8 hours ago, wtf said:

I'd expect the number of monkeys to type the CWS to be an uncountable infinity. That's because the chance of each one doing so is 1, as we've already seen. And now there are uncountably many monkeys.

As each monkey has finite volume, where would you put an uncountably infinite volume of monkeys?

If each monkey can be numbered and assigned a unique integer, can you create an uncountable list of these monkeys?

Or are most of the monkeys so bored and irrational they can be assigned zero volume and an irrational number?

(I'll eventually get round to responding to your post on another thread.)

x-posted with studiot

Share this post


Link to post
Share on other sites
1 hour ago, Carrock said:

As each monkey has finite volume, where would you put an uncountably infinite volume of monkeys?

If each monkey can be numbered and assigned a unique integer, can you create an uncountable list of these monkeys?

Or are most of the monkeys so bored and irrational they can be assigned zero volume and an irrational number?

(I'll eventually get round to responding to your post on another thread.)

x-posted with studiot

They are not meant to be actual living monkeys, for those who still wonder. 

You can number the monkeys conveniently by the real numbers in the open interval \( (0,1).\)

Test the monkeys one by one instead of in a shared location, thus no extra space needed. 

Share this post


Link to post
Share on other sites
2 minutes ago, taeto said:

You can number the monkeys conveniently by the real numbers in the open interval (0,1).

 

Why would you want to do it like that?

Share this post


Link to post
Share on other sites
16 hours ago, studiot said:

You introduced n, not I. And n is not a count of every occurrence when a sequence of n letters (there you used it differently yourself) "matches the works of Shakesspeare."

I did try to be careful by typing: "the combined works of Shakespeare amount to precisely n letters". The point is that this sequence length is the only length you want to worry about for a subsequence to be a candidate for a hit. I have not considered to make any observations of the initial sequence of the first \(n\) letters typed by the monkey, which may be what you intended, possibly. 

16 hours ago, studiot said:

A few posts back, I did define S as the exact count of letters in the works of Shakespeare, so that we could all use it for short.

And this is exactly what I replied that I would assume, that my \(n\) is equal to your \(S\). It means that for all possible choices of looking for a subsequence of length \(n,\) we can restrict to such \(n\) for which \(n=S.\) So far so good. 

Share this post


Link to post
Share on other sites
11 minutes ago, taeto said:

So far so good. 

:)  +1

Share this post


Link to post
Share on other sites
Posted (edited)
17 hours ago, studiot said:

n is count of the letters produced to date by a given  monkey, in whatever sequence they arrive.

You are being a programmer now, not a mathematician :-p.

No, the letter \(n\) is not ``defined'' or ``initialized'' to be anything in particular. Yes, I admit that in a completely different question raised by StringJunky, I used the letter \(n\) to mean that natural number which is the length of the finite sequence of letters that each of a number of monkeys would have to type in the hopes of hitting the works of Shakespeare. Incidentally, also this \(n\) is supposed to equal your \(S\). 

If I said, "if we assume that the number of bolts used in the Eiffel Tower is \(n,\) then what is the probability that \(n\) is a prime?" it does not mean that whenever I mention a natural number called \(n\) at any subsequent time in a different discussion, it has to mean that \(n\) has anything to do with the Eiffel Tower.

33 minutes ago, studiot said:

Why would you want to do it like that?

I was asked by Carrock to number the critters. I didn't really think that I needed to, but this way seems practical, i.e. for each real number between 0 and 1, there is a unique monkey with that number as its label. Got any alternative in mind?

10 hours ago, wtf said:

> Yes, a single monkey will type the works of Shakespeare on repeat with probability zero. Because the single monkey will be restricted to type a single sequence of letters, whereas there is continuum many possible sequences to choose from.

No, the probability is 1. I already explained that.. Remember the key fact is that the CWS is a finite string of symbols. It's exactly the same question as asking whether a random real number is disjunctive. It is, with probability 1. As well as normal with probability 1. So a random countably infinite strings of characters from the English alphabet contains the CWS infinitely many times with probability 1.

> But that was not the question. The question was what happens if you engage not a single monkey, but continuum infinitely many. The number of monkeys will be the same as the number of possible sequences. You expect that the expected number of monkeys to achieve the correct sequence will be equal to 1, no?

I'd expect the number of monkeys to type the CWS to be an uncountable infinity. That's because the chance of each one doing so is 1, as we've already seen. And now there are uncountably many monkeys. Almost all of them will type the CWS.

If I'm misunderstanding your question please let me know. 

      By "Shakespeare on repeat" I refer to a commonly used ancient technique on CD players (remember those?) of restarting the same CD at the moment when it reaches the end. The idea is that the monkey should type, starting from its very first typed letter, the complete works flawlessly until the end, immediately followed by repeating the exact same sequence of letters once again, and after that once more, etc. The constant repetition means that the money has to type an infinite sequence correctly, not just a finite one. 

     It is in principle the same or very similar to requiring the monkey to type the digits of \(\pi,\) that is, typing 3.141592653... correctly without stopping.

Edited by taeto

Share this post


Link to post
Share on other sites
1 hour ago, taeto said:

They are not meant to be actual living monkeys, for those who still wonder.

There are other opinions.

Does an e.g. random number generator not require space and time?

From the Shakespearian monkey/random number generator defence league website:

Quote

If you prick us, do we not bleed? if you tickle us, do we not laugh? if you poison us, do we not die? and if you wrong us, shall we not revenge?

 

42 minutes ago, taeto said:

Test the monkeys one by one instead of in a shared location, thus no extra space needed.

Each monkey would require a finite amount of time to do its thing.

In all, an uncountably infinite length of time would be required.

In a shared location, uncountably infinite volume would be required.

Either way, uncountably infinite spacetime would be required. Spacetime may be infinite, but it's not uncountably infinite.

Share this post


Link to post
Share on other sites
59 minutes ago, taeto said:

I was asked by Carrock to number the critters. I didn't really think that I needed to, but this way seems practical, i.e. for each real number between 0 and 1, there is a unique monkey with that number as its label. Got any alternative in mind?

 

You are trying to map the reals to the integers by trying to do it this way.

note my question to wtf.

3 hours ago, studiot said:

So consider the monkey typing away forever and consider the set which holds that output.

 

What do you consider the cardinality of that set to be?

 

The answer to this is the basis for my answer to your other questions to me.

You cannot have 0.5 of a monkey or 0.5 of a letter typed.

 

 

5 minutes ago, Carrock said:

In all, an uncountably infinite length of time would be required.

Why?

Share this post


Link to post
Share on other sites
13 minutes ago, studiot said:

You are trying to map the reals to the integers by trying to do it this way.

Not at all. Remember that I assume that we already reside over uncountably many monkeys in that version of the problem. I can certainly map the reals injectively to the monkeys.

17 minutes ago, studiot said:

note my question to wtf.

You cannot have 0.5 of a monkey or 0.5 of a letter typed.

I am pretty sure that wtf means to point to the entire set of possible infinite sequences that can be produced by one monkey. And to realize its magnitude, that is, cardinality.

As a simplified example, suppose the typewriter has only two keys, one for 0 and one for 1. The possible sequences of these binary digits that are candidates for being typed are in 1-1 correspondence with the real numbers between 0 and 1, if we interpret each sequence as the sequence of binary digits that follow the decimal point in the binary representation of a real number. 

If you prefer decimal representation, you may assume that the monkey has the numeric keys from 0 to 9 available instead. Either way, the possible sequences correspond to real numbers from 0 to 1. 

Share this post


Link to post
Share on other sites
Posted (edited)
40 minutes ago, studiot said:

You are trying to map the reals to the integers by trying to do it this way.

note my question to wtf.

You cannot have 0.5 of a monkey or 0.5 of a letter typed.

I presume we agree an uncountably infinite set of actual monkeys is impossible?

40 minutes ago, studiot said:
44 minutes ago, Carrock said:

In all, an uncountably infinite length of time would be required.

 

Why?

 

Use an uncountable set of points rather than the nonexistent uncountable monkeys.

Give each point a finite time, say 1 second, to do its thing.

Total time required is one second times the number of uncountable points.

That time would have a length equal to the number of points on that length.

40 minutes ago, studiot said:

You are trying to map the reals to the integers by trying to do it this way.

 

 

BTW I hope it's obvious I'm not taking this thread too seriously....

x-posted with taeto

Edited by Carrock
post I hadn't read

Share this post


Link to post
Share on other sites
Posted (edited)
28 minutes ago, Carrock said:

I presume we agree an uncountably infinite set of actual monkeys is impossible?

YES: finally we are getting somewhere! Still, we could also ask an equivalent of the same question by using nothing but formal expressions in ZFC. Some would necessarily use measure theoretic notions, like, you know, lots and lots of greek letters. I prefer to stick with the monkey business for as much as possible. 

28 minutes ago, Carrock said:

Use an uncountable set of points rather than the nonexistent uncountable monkeys.

Give each point a finite time, say 1 second, to do its thing.

Total time required is one second times the number of uncountable points.

That time would have a length equal to the number of points on that length.

If a monkey is represented by a real number in \( (0,1) \) and a typed sequence is representing a real number in \( (0,1),\) then the outcome of the entire experiment means a function \( f : (0,1) \to (0,1). \) Let us be generous and assume that as we sit and stare at these words on the screen, the function \(f\) will form in something like a minute. That is, if we want at all to assign a time duration to its creation. No, let us be even more generous and give it five minutes; you should be able to prepare a kettle of water for tea while it works.

28 minutes ago, Carrock said:

BTW I hope it's obvious I'm not taking this thread too seriously....

Don't lie please...

1 hour ago, Carrock said:

Either way, uncountably infinite spacetime would be required. Spacetime may be infinite, but it's not uncountably infinite.

If "Spacetime" is modelled at least topologically as \( \mathbb{R}^4 \) as it usually is (disregarding BH's and the time before BB), then some people might argue exactly that.

Edited by taeto

Share this post


Link to post
Share on other sites
1 hour ago, Carrock said:

I presume we agree an uncountably infinite set of actual monkeys is impossible?

I would say meaningless, rather than impossible.

The rest flows from that.

 

 

Share this post


Link to post
Share on other sites
1 hour ago, taeto said:

If a monkey is represented by a real number in (0,1) and a typed sequence is representing a real number in (0,1), then the outcome of the entire experiment means a function f:(0,1)(0,1). Let us be generous and assume that as we sit and stare at these words on the screen, the function f will form in something like a minute. That is, if we want at all to assign a time duration to its creation. No, let us be even more generous and give it five minutes; you should be able to prepare a kettle of water for tea while it works.

Experiments don't mean or create functions.

 

2 hours ago, taeto said:

Don't lie please...

You think
 

Quote

 

From this session interdict

Every fowl of tyrant wingg,

Save the eaggle, feather’d kingg:

Dam machine the g is stick'd.

 

was serious?

 

2 hours ago, taeto said:

If "Spacetime" is modelled at least topologically as R4 as it usually is (disregarding BH's and the time before BB), then some people might argue exactly that.

Extraordinary claims need references.

Share this post


Link to post
Share on other sites
26 minutes ago, Carrock said:

Experiments don't mean or create functions.

Since I am countertrolling you, I can employ the concept of a function being "created" as a rhetorical device, in a display of sarcasm. The concept of a function being "created" is ridiculous enough.

So you are absolutely right on all counts. Also the experiment to flip a fair coin absolutely does not mean a function. However, the outcome of the experiment does mean the same as a function with domain "one flip" to the set of outcomes \( \{H,T\} .\) Which is what I indicated.

 

35 minutes ago, Carrock said:

You think

Why not keep the obsequy so strict and not light-hearted? 

Share this post


Link to post
Share on other sites
4 hours ago, taeto said:

 

      By "Shakespeare on repeat" I refer to a commonly used ancient technique on CD players (remember those?) of restarting the same CD at the moment when it reaches the end. The idea is that the monkey should type, starting from its very first typed letter, the complete works flawlessly until the end, immediately followed by repeating the exact same sequence of letters once again, and after that once more, etc. The constant repetition means that the money has to type an infinite sequence correctly, not just a finite one. 

     It is in principle the same or very similar to requiring the monkey to type the digits of π, that is, typing 3.141592653... correctly without stopping.

Oh, ok. Probability is zero. Same as the idea of a real number "containing all the digits of pi." 

So now your question is, what if there are uncountably many monkeys. In other words if we have uncountably many real numbers, what's the measure of the set of those numbers ending in pi. Well let's see ... Say a sequence ends in pi. Then its first FINITE number of digits can be arbitrary. There are countably many finite sequences. So there are only countably many possible sequences that end in pi, out of uncountably many possible sequences. Measure zero. Probability zero. 

What do you think?

Share this post


Link to post
Share on other sites
Posted (edited)
1 hour ago, Carrock said:

Extraordinary claims need references.

Excellent idea. If you claim that any region of \( \mathbb{R}^4\) is not uncountably infinite, it is very extraordinary and needs references. I will not hold my breath.

Edited by taeto

Share this post


Link to post
Share on other sites
Posted (edited)
7 hours ago, studiot said:

I'm sorry there are incorrect statements in your postings in  this thread.

A Continuum

Def:- A compact connected set.

The integers are not connected.

The monkeys never type 0.5 characters or 10.378 characters.

 

One of the great achievements of Cantor was to remove the need to worry about potential v actual infinities.

He pointed out that it doesn't matter that you can't practically go on typing forever.

But you can specify a set which contains the entire output of such an infinite process.

I have been considering such a set in this case.

 

So consider the monkey typing away forever and consider the set which holds that output.

 

What do you consider the cardinality of that set to be?

 

The answer to this is the basis for my answer to your other questions to me.

 

 

How can this be?

> I'm sorry there are incorrect statements in your postings in  this thread. 

No, unless minor typos. I stand by everything I've written here. 

 

> A Continuum

> Def:- A compact connected set.

Really? So the real numbers aren't a continuum? Whateva dude.

 

> He pointed out that it doesn't matter that you can't practically go on typing forever.

No, it was Russell who invented type theory. [That was a joke].

 

> The integers are not connected.

Um ... what does that have to do with anything?

 

>  So consider the monkey typing away forever and consider the set which holds that output.

> What do you consider the cardinality of that set to be?

We're modeling the output of a monkey as a countably infinite string of symbols, same as the decimal representation of a real number.

Edited by wtf

Share this post


Link to post
Share on other sites
Posted (edited)
12 minutes ago, wtf said:

Oh, ok. Probability is zero. Same as the idea of a real number "containing all the digits of pi." 

So now your question is, what if there are uncountably many monkeys. In other words if we have uncountably many real numbers, what's the measure of the set of those numbers ending in pi. Well let's see ... Say a sequence ends in pi. Then its first FINITE number of digits can be arbitrary. There are countably many finite sequences. So there are only countably many possible sequences that end in pi, out of uncountably many possible sequences. Measure zero. Probability zero. 

What do you think?

It does not quite fly, I think.

For simplicity, I suggest to just focus on the event that the successful monkey manages to type the entire sequence of the digits of \(\pi\) starting from 3.14... and ending, hm, not...

For a single monkey, yes, unlikely.

The question is what will happen if you have a pretty large crew of monkeys working away. Enough that it seems that in unison they can beat the odds. 

Really, there is only continuum many possible infinite sequences. Surely if you have a crew of \( 2^c \) monkeys working at it, where \(c\) is the cardinality of the continuum, then a host of monkeys will hit the right answer, right? But is there some reason that you would need that many?

Edited by taeto

Share this post


Link to post
Share on other sites
Posted (edited)
8 minutes ago, taeto said:

It does not quite fly, I think.

For simplicity, I suggest to just focus on the event that the successful monkey manages to type the entire sequence of the digits of π starting from 3.14... and ending, hm, not...

For a single monkey, yes, unlikely.

The question is what will happen if you have a pretty large crew of monkeys working away. Enough that it seems that in unison they can beat the odds.

Seems that I crossposted with you.

I answered the question correctly, now that I've had a little time to rethink it. 

How many real numbers end in the digits of pi? Remember, pi must be the ENTIRE TAIL of the number. So only the first FINITELY MANY digits are unconstrained. There are only countably many finite sequences of digits. So the class of all real numbers that end in pi is countably infinite. This seems perfectly correct.

In other words, what do some of these reals look like? .123pi, .343424324332pi, .50438590438590430958430pi, etc. Every possible finite sequence, followed by the digits of pi. There are exactly a countably infinite number of these. 

Out of an uncountable collection of monkeys generating random real numbers, only countably many of those reals will end in pi. Because there aren't any more than that to be found. But there are uncountably many reals. 

Look at it yet another way. Every such real looks like this:

(terminating rational) followed by the digits of pi.

There are only countably many terminating rationals.

Edited by wtf

Share this post


Link to post
Share on other sites
2 minutes ago, wtf said:

I answered the question correctly, now that I've had a little time to rethink it. 

How many real numbers end in the digits of pi? Remember, pi must be the ENTIRE TAIL of the number. So only the first FINITELY MANY digits are unconstrained. There are only countably many finite sequences of digits. So the class of all real numbers that end in pi is countably infinite. This seems perfectly correct.

Which to me still seems to argue, however correctly, that it is impossible for a single monkey to achieve the goal, and also for any countably infinite number of monkeys as well. But it does not seem to argue convincingly, why not at least one of uncountably many monkeys might get lucky?

Share this post


Link to post
Share on other sites
Posted (edited)
6 minutes ago, taeto said:

Which to me still seems to argue, however correctly, that it is impossible for a single monkey to achieve the goal, and also for any countably infinite number of monkeys as well. But it does not seem to argue convincingly, why not at least one of uncountably many monkeys might get lucky?

They might get lucky with probability zero. A single monkey might get lucky with probability zero. Remember that probability zero doesn't mean impossible, it just means probability zero. Like the rationals in the reals.

Do you agree that there are only countably many reals whose decimal representation ends in pi? Because there can be only a finite sequence of digits preceding the point where pi starts. And there are only countably many finite strings of digits. You agree?

 

Edited by wtf

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

×
×
  • Create New...

Important Information

We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.