Infinite monkeys and Shakespeare

[StringJunky]

7 minutes ago, wtf said:

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.

Can you elaborate this in layman terms?

[wtf]

4 minutes ago, StringJunky said:

Can you elaborate this in layman terms?

The bolded part? The measure of the rationals in the reals is zero. If you "throw a dart at the real line," or randomly pick a real number out of a hat, the probability that the number you pick is rational is zero. Yet you might get lucky and pick a rational. In infinite probability theory, probability zero doesn't mean an event is impossible; and probability 1 doesn't mean that it's certain. 

As a (perhaps) intuitively visualizable example, suppose I flip a fair coin infinitely many times. The probability that they're all heads is zero. Yet there's no reason why they couldn't all be heads. It's just really really unlikely. As unlikely as the sequence of coin flips representing a rational number in binary [with a binary point in front of the sequence so that it represents some real number in the unit interval].

Edited March 5, 2019 by wtf

[StringJunky]

3 minutes ago, wtf said:

The bolded part? The measure of the rationals in the reals is zero. If you "throw a dart at the real line," or randomly pick a real number out of a hat, the probability that the number you pick is rational is zero. Yet you might get lucky and pick a rational. In infinite probability theory, probability zero doesn't mean an event is impossible; and probability 1 doesn't mean that it's certain. 

As a (perhaps) intuitively visualizable example, suppose I flip a fair coin infinitely many times. The probability that they're all heads is zero. Yet there's no reason why they couldn't all be heads. It's just really really unlikely. As unlikely as the sequence of coin flips representing a rational number in binary. 

Right. OK. Thanks.

[wtf]

 

1 hour ago, StringJunky said:

Right. OK. Thanks.

Hope that was helpful. I searched for a simple online explanation but found nothing. The Wiki article on probability theory doesn't say anything about this topic, and searches on "infinitary probability theory" brought up advanced academic articles.

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

But the Wiki article did mention the connection to abstract integration theory. So if you took calculus, then you know that even for the Riemann integral, changing the value of one point doesn't matter. If I have some function defined on the unit interval whose integral is 47, say; then another function that differs from the first at only one point has the same integral. It's also not hard to prove that you can change the value at any countable set of points without changing the integral; and in fact you can change the value on any set of measure zero without changing the value of the integral. [I don't recall and didn't feel like looking up whether that last statement applies to the Riemann integral or only to the more advanced Lebesgue integral].

Modern probability theory is based on modern abstract integration theory. Everything you can say in probability theory is only true "up to a set of measure zero." This situation comes up so much that we have the terminology "almost all," or "almost surely," attached to a lot of theorems. 

As a familiar example, it's mathematically correct to say that almost all real numbers are irrational. "Almost all" is a technical term meaning, "all but a set of measure zero." We can view this as a probability. If we "randomly pick a real number," it will almost surely be irrational. Even though the rationals are sitting there saying, "Pick me, pick me!" There just aren't enough of them to make any difference in the scheme of things.

[This is true even though the rationals are dense in the reals; that is, there's a rational between any two reals. This is an intuitive paradox but not actually a mathematical paradox. It's just one of those strange things you get used to].

So all of this is just a natural extension of the fact from freshman calculus that integrals are about behavior in the limit; and they allow for many individual points of exception to the statistical certainties; which should always be understood to be almost certainties.

Here's a math.stackexchange thread on the subject.

https://math.stackexchange.com/questions/41107/zero-probability-and-impossibility

It's worth mentioning that these ideas bear on the speculative physics of "many worlds" and related ideas. People say that if there are infinitely many universes then "everything must happen." This is false for the same reason. You can flip infinitely many coins and have them be all heads. There's no reason why not. Likewise you can have many exceptions to the rule of "everything" happening in a multiverse; likewise measure zero events can happen. Like life on earth, maybe. It's important to remember that all such infinitary arguments are essentially statistical arguments and do not prohibit individual exceptions.

Edited March 5, 2019 by wtf

[Strange]

32 minutes ago, wtf said:

As a familiar example, it's mathematically correct to say that almost all real numbers are irrational. "Almost all" is a technical term meaning, "all but a set of measure zero." We can view this as a probability. If we "randomly pick a real number," it will almost surely be irrational. Even though the rationals are sitting there saying, "Pick me, pick me!" There just aren't enough of them to make any difference in the scheme of things.

There is a bit of discussion of this here: https://www.quantamagazine.org/why-mathematicians-cant-find-the-hay-in-a-haystack-20180917/ (not sure if it adds anything, other than the observation that we are more familiar with the infinitely rare rationals because we can write them down)

[wtf]

1 hour ago, Strange said:

There is a bit of discussion of this here: https://www.quantamagazine.org/why-mathematicians-cant-find-the-hay-in-a-haystack-20180917/ (not sure if it adds anything, other than the observation that we are more familiar with the infinitely rare rationals because we can write them down)

Great article, thanks. Yes that's a really interesting point. We're so much more familiar with the everyday rationals, even though they are the great outliers in the reals.

That's another interesting thing about the normal numbers. The normal numbers are real numbers whose decimal representation has every finite string a statistically equal number of times. It's been proven that almost all (all but a set of measure zero) real numbers are normal. 

However, very few real numbers have been proven normal. When people speculate that "Pi contains the names of all the people you will ever know," which is a meme that was floating around a while back, they're assuming that pi is a normal number. But in fact that's an open problem. Nobody has any idea if pi is normal.

[Edit - as with Shakespeare and the monkeys, that requires pi to be a disjunctive number, a point many online are confused about. I didn't want to add to that confusion. If all we need is for every finite sequence to appear at least once, that's disjunctive].

 

Edited March 6, 2019 by wtf

[Eric H]

13 hours ago, Janus said:

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

Fair enough, but I fail to see the purpose of such an exercise.

[wtf]

8 minutes ago, Eric H said:

Fair enough, but I fail to see the purpose of such an exercise.

It's a popularized fable to give people a feel for the mathematical infinite. Sort of like Hilbert's hotel, which is an infinite hotel that can nevertheless accommodate infinitely many new guests without having to displace anyone. Sort of like a rubber sheet with gridlines drawn on it, and a bowling ball in the center pulling the sheet down, showing how mass distorts space to create gravity. Of course the question is ... what pulls the bowling ball down? So these stories should not be taken for science; but rather, as science-y fables. 

[Eric H]

36 minutes ago, wtf said:

So these stories should not be taken for science; but rather, as science-y fables. 

The science-y fable we all strive to understand is something with no beginning; or something that did not come from anything.  

[taeto]

14 hours 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?

If each of infinitely many monkeys types a random sequence of \(n\) letters, then with probability 1, every possible sequence of length \(n\) will be typed by infinitely many of them.

[studiot]

15 hours 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?

 

18 minutes ago, taeto said:

If each of infinitely many monkeys types a random sequence of n letters, then with probability 1, every possible sequence of length n will be typed by infinitely many of them.

 

Some further thoughts.

With monkeys, typewriters and letters we are talking the statistics of a discrete variable of integers, not the statistics of real numbers.

String Junky, in suitable circumstances.
But you would have a problem ordering the monkeys.
An infinite amount of monkeys would produce enough letters for every sequence (ie an infinite amount of letters), if they all typed one letter apiece.

This would obviously include the finite set comprising the complete works of Shakespeare.

But how would you know which set of monkeys to choose from, before they started typing?
You would have to discard an infinite amount of typing to be left with a finite set.

 

There is one other interesting thing about infinity that comes up here.

One of the basic (and original) identifiers of infinity was that the 'part contains the whole'.

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.

The issue of how long in time this would take is an irrelevant red herring.

[taeto]

3 hours ago, Eric H said:

The science-y fable we all strive to understand is something with no beginning; or something that did not come from anything.  

Who are your "we"?

If striving isn't one's favorite hobby, one can imagine that any current something, call it something(0), came from another something, something(1), which in turn came from a something(2), and so on. Then every something has a beginning and comes from another something. 

I have to go watch the new episode of the Big Bang Theory now. Will the series never end? 

34 minutes ago, studiot said:

She would also type out all the (infinite) characters of Pi. Remember the sequence of Pi never repeats.

But careful with this. Assuming she can type alphanumeric characters instead of spelling out the decimal digits (are numerals needed for Shakespeare?) it is true that she will at some point type "3", and some time later "3.1", and later again "3.14" etc. For every \(n\) she will type the initial \(n\) digits of \(\pi\) at some point. But never the infinite sequence of all the digits. 

Edited March 6, 2019 by taeto

[chrisnhowell]

I am no mathematician and I clearly don't understand probability theory as is apparent by my original post.

Does it not come down to the idea that it is 'possible' to throw a fair coin and it infinitely land on heads?

As a side issue; our descriptions of time like eventually, in the end etc become meaningless in regard to infinity. 'Instantaneous' and 'eventually' mean the same thing.

[taeto]

22 minutes ago, chrisnhowell said:

Does it not come down to the idea that it is 'possible' to throw a fair coin and it infinitely land on heads?

Basically yes. It is 'possible', because for the experiment to make sense, we have to allow some outcomes to be 'possible', and it does not make sense to allow Tails to be possible at the time of any particular flip without also allowing Heads to be possible. That immediately makes the all Heads outcome a possibility. However, if the experimenter reports that the outcome turned out to be all Heads, your proper reaction is to exclaim "impossible!" The reason is that it is 100% certain that the experimenter will be unable to report the exact outcome of the experiment by making a statement that has a finite length. 

[studiot]

53 minutes ago, chrisnhowell said:

I am no mathematician and I clearly don't understand probability theory as is apparent by my original post.

Does it not come down to the idea that it is 'possible' to throw a fair coin and it infinitely land on heads?

As a side issue; our descriptions of time like eventually, in the end etc become meaningless in regard to infinity. 'Instantaneous' and 'eventually' mean the same thing.

This is why I was making the point that 'infinity' is a funny thing which ahs some non intuitive properties.

Notice that taeto is being very careful to refer to n charcters or n coin tosses.

Any sequence of n characters or tosses is finite.

But you has specified an infinite sequence of characters or tosses.

1 hour ago, taeto said:

But careful with this. Assuming she can type alphanumeric characters instead of spelling out the decimal digits (are numerals needed for Shakespeare?) it is true that she will at some point type "3", and some time later "3.1", and later again "3.14" etc. For every n she will type the initial n digits of π at some point. But never the infinite sequence of all the digits. 

 

I however did specify the infinite sequence of Pi, deliberately to invoke the particular peculiar properties of infinity.

 

If you are going to limit your monkeys to finite sequences only, that is a different model you should be using.

You should also specify a stopping criterion.

Further you will not be able to fit the output of your infinite collection of monkeys into any finite set.

Edited March 6, 2019 by studiot

[taeto]

2 minutes ago, studiot said:

I however did specify the infinite sequence of Pi, deliberately to invoke the particular peculiar properties of infinity.

That is how your statement appeared to read, and I am trying to point out that this would be incorrect.

However 'possible' the infinite sequence of digits is, it has probability zero to occur uninterrupted. The most you can do is to have it appear with interruptions between the digits in the form of irrelevant subsequences.

9 minutes ago, studiot said:

If you are going to limit your monkeys to finite sequences only, that is a different model you should be using.

I assume one monkey typing away without ever stopping.

[studiot]

25 minutes ago, taeto said:

I assume one monkey typing away without ever stopping.

But you wrote this

2 hours ago, taeto said:

If each of infinitely many monkeys

 

The point is that we are mapping from the output set to the set of sequences.

For one monkey we do not require an infinite set, since the ouput of one monkey is always finite.

Further the original requirement in the OP was for a finite sequence.

 

But for an infinite set of monkeys the first output is necessarily infinite so the output set must be infinite.

 

So there is a difference between one monkey and an infinite time and an infinite set of monkeys and however much time, finite or infinite.

[taeto]

1 hour ago, studiot said:

The point is that we are mapping from the output set to the set of sequences.

For one monkey we do not require an infinite set, since the ouput of one monkey is always finite.

Further the original requirement in the OP was for a finite sequence.

 

But for an infinite set of monkeys the first output is necessarily infinite so the output set must be infinite.

 

So there is a difference between one monkey and an infinite time and an infinite set of monkeys and however much time, finite or infinite.

When you typed:

"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."

I tried to point out that it would be incorrect to state that she would type out the entire (uninterrupted) sequence of digits of \(\pi.\)

There is a discussion on monkeys typing \(\pi\) on 

math.stackexchange.com/questions/1232394/infinite-monkey-problem-probability-of-an-infinite-sequence-containing-an-infi?rq=1

StringJunky remarked about the case of infinitely many monkeys:

"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?"

And I tried to answer by saying that if we have an infinite amount of monkeys, then we can even impose a stopping criterion, that each monkey has to stop after only typing as many characters as there are in Shakespeare's combined works, and we are still ensured to have infinitely many of the monkeys returning the perfect script. The case when the monkeys are not allowed to stop ought to result in the outcome that every monkey produces infinitely many copies of the works, right? Now that I type this I get unsure. Let it be a question:

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?

Edited March 6, 2019 by taeto

[studiot]

27 minutes 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.

30 minutes ago, taeto said:

And I tried to answer by saying that if we have an infinite amount of monkeys, then we can even impose a stopping criterion, that each monkey has to stop after only typing as many characters as there are in Shakespeare's combined works,

and you didn't actually say that before

3 hours ago, taeto said:

If each of infinitely many monkeys types a random sequence of n letters, then with probability 1, every possible sequence of length n will be typed by infinitely many of them.

 

 

Thinking further the most thorough scenario is that of an infinite crew of monkeys each typing a set of n characters with n = Shakespeare.

Then we will have infinite copies of the complete works along with stranger manuscripts like the first n/2 words repeated and so on.

[taeto]

15 minutes ago, studiot said:

None of us are being entirely rigorous here.

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

You are correct, I asked for "the probability". It is true that such a probability does not necessarily exist.

But if "it depends", as you say, then it means that you expect infinitely many monkeys to not have completed the assignment. Otherwise there would be a definite probability, namely 0. How did you see that, and so quickly?  

[studiot]

44 minutes ago, taeto said:

You are correct, I asked for "the probability". It is true that such a probability does not necessarily exist.

But if "it depends", as you say, then it means that you expect infinitely many monkeys to not have completed the assignment. Otherwise there would be a definite probability, namely 0. How did you see that, and so quickly?  

Not sure I understand the question.

[taeto]

29 minutes ago, studiot said:

Not sure I understand the question.

Sorry, I was too quick. I realize you are here and there and everywhere in the forum. It is not always easy to keep track of single threads.

I suggested, in the same vein as StringJunky's question, that 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?

I thought that you reacted by saying "it depends". And that can make sense. But only if you expect that infinitely many monkeys will fail the test. If the number of monkeys to fail is a natural number, then the answer does not depend on how you order the outcomes.

17 hours ago, wtf said:

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.

I only saw this now, sorry.

But you do not address the question as it was posed.

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?

Edited March 6, 2019 by taeto

[studiot]

12 minutes ago, taeto said:

then the answer does not depend on how you order the outcomes.

It wasn't a question of ordering, it was a question of partitioning the output set.

1) Would you say that you divide the output set into finite subsets with n=S such that every subset has n = S ?

2) Or would you parse the output set until the first character of Sheakespeare appeared (I don't know what it is, say it is an H) then count correct characters until either n = S or an incorrect character appears, at which point you would start again waiting for the next H. So the subsets would be of variable cardinality.

3) Or would you parse the first n characters and discard if incorrect, then the next n characters and discard if incorrect .......
That is all subsets would have fixed cardinality.

4) Or something else I haven't thought of.

[peterwlocke]

it could happen 

[taeto]

2 hours ago, studiot said:

It wasn't a question of ordering, it was a question of partitioning the output set.

1) Would you say that you divide the output set into finite subsets with n=S such that every subset has n = S ?

2) Or would you parse the output set until the first character of Sheakespeare appeared (I don't know what it is, say it is an H) then count correct characters until either n = S or an incorrect character appears, at which point you would start again waiting for the next H. So the subsets would be of variable cardinality.

3) Or would you parse the first n characters and discard if incorrect, then the next n characters and discard if incorrect .......
That is all subsets would have fixed cardinality.

4) Or something else I haven't thought of.

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.