27

I've seen a few different formulations of this, but the most famous is "monkeys on a typewriter" - that if you put a team of monkeys on a typewriter, given infinite time, they will eventually produce the works of Shakespeare, and indeed every text ever written or even conceivable. (Other arguments I've seen include: if the Universe is infinite, there must be a planet exactly like ours somewhere. I'll stick to the monkeys for the sake of this argument.)

I've always been sceptical of this, but it's just occurred to me why - I wanted to ask if my thinking stands up to scrutiny, or if there is a counterargument.

If you have a sequence of coin flips, the probability of heads or tails is always 50:50, no matter the previous sequence. Even if we get a sequence of 10 heads in a row, the probability of the 11th coin flip is still 50:50. Believing otherwise is to engage the gambler's fallacy - the belief that if a particular event happens more frequently than normal, it's less likely to happen in the future.

So here's my thinking. Say that a decision can have one of two outcomes, A or B, and they're equally likely, 50:50 chance of occurring. Then based on outcome A or B, there are a further two outcomes that could happen - if it's outcome A, you could have outcome C or D (both equally likely,) or if it's outcome B, you could have outcome E or F (both equally likely.) So the probability of arriving at outcome C, D, E or F is 25%, after taking just two decisions.

If you made 1,000,000 similar decisions, the probability of that final outcome being reached at any one moment is 1 in a million. The larger the number of decisions, the closer the probability approaches to zero - if there were infinite decisions, the probability of any one outcome would converge on zero.

Now to me, the "monkeys on a typewriter" genre of arguments seems to be saying that if you take that decision tree and stretch it over an infinite timeline, eventually you will reach all the outcomes on the decision tree. But to me, that doesn't add up. If there are 1 trillion possible outcomes, the possibility of one particular outcome is always 1 trillion - it will never become more likely simply due to the passage of time. And so you might literally never reach one of Shakespeare's plays by simply hoping that random keypresses will converge on that 1 in a trillion outcome. Because it's just so unlikely.

Is this a fair criticism, or is there more to the "every outcome will happen in an infinite timeline" argument that I hadn't considered? Note that I'm not very mathematically numerate or logically literate - I'd be extremely grateful if complex formulae were either kept to a minimum or explained in layman's terms.

  • 10
    Are you familiar with the concept of limits in calculus? The probability that a sequence of N coin flips will fail to contain a single tail approaches 0 in the limit as N approaches infinity (for 2 flips, prior to either flip having been done, the probability of getting no tails is 1/4; for 3 flips, it's 1/8; for 4 flips, it's 1/16 etc.), so if someone bases their argument on that I don't see how it resembles the gambler's fallacy. – Hypnosifl Jan 30 at 16:04
  • 23
    Your confusion here may arise because we as humans find it impossible to comprehend "an infinite amount of time" as a completed whole. – Nick Jan 30 at 16:59
  • 5
    Are you considering the probability of full sequences? The kind of argument you mention is about the probability of sequences containing finite strings of characters. The probability of getting exactly one of Shakespeare's play from the start is indeed very low, but the probability of a random sequence containing one of Shakespeare's play at any position becomes closer to one as the size of sequences increases. – Quentin Ruyant Jan 30 at 18:09
  • 1
    It could happen and it would happen. But infinity will not occur because ∞ is not a number. – Mazura Jan 30 at 23:25
  • 1
    To add to @Lou’s comments, the “laws of probability” seem to match experience in things we can measure. So we have “faith” that they can predict things we can’t measure. And we can’t really disprove them empirically, because they actually predict the possibility of an unexpected result. – WGroleau Jan 31 at 17:26

10 Answers 10

14

Here, I think, is a more succinct answer:

Let's say we have a dice with 1 trillion sides. Then, the probability of a given outcome on the next roll of the dice is one-in-a-trillion.

On the other hand, the probability of getting a given outcome, at least once, given infinite dice rolls approaches 1.

Given enough time, monkeys banging randomly at a typewriter will produce the works of Shakespeare

This not an instance of the gambler's fallacy—the likelihood of this happening at least once, given infinite dice rolls does not increase or decrease based on what happened before it. The liklihood of it happening at least once increases based on the amount of time you give it (which is not what the gambler's fallacy is!)

Similarly: The chances of getting tails on the next coin flip is always 50%. But, given enough coin flips, someone flipping a coin will get tails.

| improve this answer | |
  • 2
    Ah okay, I think this explanation actually helped me to understand the most. In particular this: "This not an instance of the gambler's fallacy—the likelihood of this happening at least once, given infinite dice rolls does not increase or decrease based on what happened before it. The liklihood of it happening at least once increases based on the amount of time you give it" So probability will naturally increase over time, but not as a result of events that came before it? – Lou Jan 31 at 14:15
  • 1
    @Lou Correct! The events that came before it don't actually matter. There are other examples of this too: given enough time, life is bound to eventually pop up on some planet. ;) – AmagicalFishy Jan 31 at 16:31
  • 1
    @Lou To clarify "probability will naturally increase over time" - let's say that something has a 25% chance of happening within 5 minutes, and a 50% chance of happening within 10 minutes. If 5 minutes pass and the thing has not happened, the chance of it happening in the next 5 minutes has not become 50% (this would be gambler's fallacy). We must ignore past events, so it still has only a 25% chance of happening given only 5 more minutes. I think you got it, but wanted to clarify that probability doesn't increase as time passes, it just increases based on how much time will pass. – charmingToad Jan 31 at 22:01
  • 1
    I've read all the answers and they all ultimately helped me to understand the concepts that I was confusing, but I accepted this one because it was the most clear and concise, and helped me to understand the most. Thanks to all the other contributors! – Lou Feb 1 at 10:34
  • 1
    @charmingToad: Note that if something has a 25% chance of happening in any given five minutes, then it has only a 44% chance of happening in any given ten minutes, rather than a 50% chance. (This is because (1 − 0.25)² ≈ 1 − 0.44.) But other than that -- good comment, +1. :-) – ruakh Feb 1 at 23:40
41

It looks like you've hit upon the concept of almost surely in probability theory. Something occurs "almost surely" if it happens with probability 1, but there still exist situations where that thing does not occur. The infinite coin flips problem is a great example - with infinite coin flips, you will almost surely see at least one result of heads, that is, the probability that you get at least one heads is 1. There is, however, the possible situation where you get an infinite sequence of tails - it's not explicitly impossible for this to happen. But, since there are an infinite number of sequences that have at least one head, and only one sequence with no heads, the probability of getting that infinite sequence of tails is 1/X in the limit of X going to infinity, which is 0.

Similarly, with the infinite monkeys, there is some finite number of texts that can be written with normal punctuation and lettering that have the same length as Hamlet, about 130,000 characters. Now the probability of failure is much, much higher than the coin flip, but that doesn't matter with infinite tries. As you try more and more times, the likelihood that you fail every single time gets smaller and smaller, falling to 0 as you try an infinite number of times. It is possible that you never type out Hamlet even if you type forever, but you will almost surely type it at some point with probability 1. Note that this isn't unique to the text of Hamlet - in any infinite sequence of characters, you will almost surely see every finite sequence of characters. An infinite number of monkeys will almost surely type out Hamlet, but they'll also almost surely type out Hamlet with the protagonist's name replaced with "butthead", and a version of Hamlet where he gets into a rocket ship at the end, and every other variation you can imagine.

This isn't the gambler fallacy, which assumes that past outcomes can influence future ones for independent events. In an infinite sequence of events, the likelihood of an event at any point in the sequence never changes. We know that for each sequence of 130,000 random characters, the odds that it spells out Hamlet it exceedingly unlikely. The fact that we don't see it many times doesn't make it any more likely that we'll see it the next time. It's simply the case that with enough tries, you will eventually, almost surely, write out Hamlet - no matter how biased your coin is, it's almost sure that you will not see a tails every single time if you keep flipping it forever.

This isn't the Gambler's Fallacy, but does lead to something called the Gambler's Ruin. Any player with finite wealth playing a fair game will eventually go bankrupt when playing against someone with infinite wealth (effectively the casino), because in an infinite sequence of games, it is almost sure that at some point, the gambler will encounter a series of losses that will be sufficient to bankrupt him.

| improve this answer | |
  • 19
    Side note: "Almost surely" is not just a matter of finite vs infinite. For example, if you pick a random real number between (say) 0 and 1, it will "almost surely" be irrational, even though they are infinite rationals to choose from. The intricacies of infinities like this are usually introduced in undergraduate Real Analysis courses. – BlueRaja - Danny Pflughoeft Jan 31 at 1:46
  • 4
    @3ocene There's a concept in real analysis called "measure" that is rather too complicated to get into in a comment, but given the standard measure, one way to show that the number is "almost surely irrational" is to note that rational numbers are enumerable (it's possible to assign integers to each rational number so that each rational number gets a different integer). – Acccumulation Jan 31 at 7:15
  • 6
    With the monkeys example, library of babel comes to mind (parentheses mine): If completed, it would contain every possible combination of 1,312,000 characters, including lower case letters, space, comma, and period. Thus, it would contain every book that ever has been written, and every book that ever could be - including every play, every song, every scientific paper, every legal decision, every constitution, every piece of scripture, and so on. At present it contains all possible pages of 3200 characters, about [10 to the power of 4677] books. here's a link: libraryofbabel.info – John Hamilton Jan 31 at 8:19
  • 3
    @Lou That's pretty much correct. The likelihood of an infinite typist never typing Hamlet is exactly the same as the likelihood of an infinite flipper never seeing heads - both are 0. As long as your event (typing Hamlet or seeing heads) is possible (having non-zero probability), no matter how unlikely, if you try an infinite number of times, it is almost sure that you will not fail every single time. If your likelihood of success on one trial is p (0<p<1), the likelihood of no successes on N trials is (1-p)^N, which always goes to zero as N goes to infinity, regardless of how small p is. – Nuclear Hoagie Jan 31 at 14:25
  • 2
    @Accumulation That there are more irrationals than rationals is more directly related to cardinality than to measure. But this is beside the point: infinities get complicated and often behave in unintuitive ways (Hilbert's Hotel, Banach-Tarski paradox, etc.) – aschepler Jan 31 at 20:21
11

"If you made 1,000,000 similar decisions, the probability of that final outcome being reached at any one moment is 1 in a million."

That quote represents the root of your misconception. If a coin is tossed 1 million times, the likelihood of any specific sequence of 1 million tosses is 1 in 2^1000000. However, the chances of tossing heads 10 times in a row anywhere in that million are much much better; much better than tossing heads 10 times in a row in 10 tosses. The chances 10 heads not happening on the first 10 tosses is 1023/1024, the chances of it not happening on neither the first ten tosses nor the second is (1023/1024)^2, the chances of it not happening in any of the sequential groups of 10 (tosses 1-10, 11-20, 21-30, and so on) for 1 million tosses is less than 4*10^-43.... and that is ignoring that 10 heads in a row could happen on tosses 2-11, 3-12, and so on.

"Monkeys typing Shakespeare" is simply an expansion of this observation. It would use a die with enough sides to include every character, space, punctuation mark, and any other typographic symbols used in those works; and much much more than 1 million tosses.

However, there is another fallacy in play, though I am not sure there is a name for it. Random sequences are necessarily capable of representing all combinations. If the monkeys' typewriters have had their vowels removed, or the vowel keys always double typed, not even a sentence of Shakespeare could be produced.

| improve this answer | |
  • +1 but I don't follow what point you are making in the final paragraph? It seems to just confirm that the event needs to have a probability greater than zero for it to occur in an infinite number of attempts. – JBentley Jan 31 at 1:19
  • 6
    "If the monkeys' typewriters have had their vowels removed, or the vowel keys always double typed, not even a sentence of Shakespeare could be produced." However, there may be a mapping from a sequence of generated letters to the works of Shakespeare, such as a binary or other similar encoding. – JAB Jan 31 at 1:25
  • Thanks for reminding me about the probability of the coin toss. So basically what you're saying is, as the "sample size" increases (number of coin tosses, number of monkey keypresses, not sure what the probabilistic term for this is,) the likelihood of a given sequence occurring does increase? I think I'm still struggling to understand why this notion isn't the same as the gambler's fallacy. – Lou Jan 31 at 14:04
  • 4
    @JAB: Give me any arbitrary dataset (A) and ask for whatever you want (B) and I will give you a list of mapping rules that returns B with A as its input (disclaimer: unexpected behavior for any other input value). Injecting an arbitrary mapping into the monkey-typewriter situation nullifies the importance of the thought exercise. – Flater Jan 31 at 15:48
  • 1
    The last paragraph makes more sense in a mathematical context: we have no guarantee that every finite sequence appears in (for instance) pi. It's entirely possible that we could put odds on a given sequence appearing and find that it's less than one. We can't at the moment, because we can't say enough about the digits of pi. – Spitemaster Jan 31 at 17:14
8

You're right about the gambler's fallacy, but you're missing something essential about infinity. Infinity doesn't stop.

So, you've got your immortal monkey and his endless reams of typewriter supplies, and a typewriter with 40 keys. He endlessly hammers on the keys perfectly randomly.

The probability that he types a "T" on the first try is 1/40.
The probability that he types a "T" in the first 2 tries is 1-(39/40)^2, or about 1/20.
The probability that types a "T" in the first 40 tries is 1-(39/40)^40, or about 63%.
It keeps growing. The probability that he gets it in the first 400 tries gets as high as 99.996%.

You're right that the gambler's fallacy is to be avoided, and what that means is that if he doesn't hit a "T" in the first, let's say, 10 attempts, then his chance of hitting it on 11, or between 11 and 12, or between 11 and 50, or between 11 and 411, is still 1/40, 1/20, 63%, and 99.996% respectively.

Now, when we say the probability of hitting a "T" if he hits the typewriter randomly infinitely many times is 1, we're not denying that the gambler's fallacy is wrong. We agree that with independent random events, what has happened before does not change the probabilities of what will happen next. It's just that in the same way as after missing "T" 10 times, the odds of getting it in the next 1, 2, 40, or 400 don't change, so likewise after missing 10 times the odds of getting it in the next infinity presses doesn't change.

The probability that he types out a "T" followed by a "H" is one in 1600. The probability that he does so at some point in the first 3200 taps is about 63%.

The probability that he types out just the phrase "Two households, both alike in dignity" is one in 40^37, which is starting towards those vanishingly unlikely things that starts to wear out the universe before you get to it. The chance of typing all of Shakespeare is unfathomable. But if you have genuinely infinite chances, that's much larger than the expected lifetime of the universe. If it doesn't happen in the first lifetime of the universe, who cares? You still have infinitely many universe lifetimes to go!

| improve this answer | |
  • 1
    Well written, but a small clarification may be in order: "we're not denying the gambler's fallacy is true". I understand that you mean to say that we're not denying that the outcome of an event is independent of the outcome of previous events, but it can sound like you're saying that a fallacy is true. – Bjonnfesk Jan 31 at 7:16
  • Thanks. Updated – Josiah Jan 31 at 8:16
  • 4
    I think I understand now. Are you saying that, the odds of getting sequence X will always increase as the numbers of attempts (keypresses, coin flips etc.) increases, but that this increase in probability has nothing to do with the outcome of previous attempts? – Lou Jan 31 at 14:13
  • 1
    Basically, a gambler with infinite funds never runs out of funds and can continue trying to beat the bank. – ceejayoz Jan 31 at 14:40
  • 1
    Precisely. Infinity is a bigger thing than most people imagine. (Are there some infinite sequences that don't include Hamlet as a substring? Yes. But only if they are non-random.) – Michael Kay Jan 31 at 17:49
2

This isn't a full answer, but I'd like to point out that you've formulated an alternate version of Zeno's Paradox. As the amount of time increases, the probability that some rare event does not occur becomes smaller and smaller but is never exactly zero. This is similar to how Zeno moves ever closer to but never reaches the target destination. Nonetheless, once you sum the infinite number of movements in the sequence, the destination is reached. Likewise, over an infinite amount of time, the rare event must occur.

| improve this answer | |
  • Yeah, that definitely helps me to understand the apparent paradox. What I wasn't understanding - and others have clarified - is the idea that the probability of an event occurring increases over time, but not based on the outcome of a previous event. – Lou Jan 31 at 16:04
  • Even the infinite sum is not equal to the target. It is infinitesimally smaller than the target. The probability of missing a given state, while infinitesimal, is still nonzero, so the "must occur" argument is not quite accurate, since the event is missing some of its probability. – pygosceles Jan 31 at 18:52
  • 1
    @pygosceles That's not quite correct. Zeno actually does reach the tree. – Jeff Y Jan 31 at 19:08
  • Yes, but only because he is in a physical environment where inexactness is tolerated. Mathematically, he never reaches it. For practical purposes in a physical world, where there are limits on precision of observation, he does. – pygosceles Jan 31 at 19:35
  • 1
    @pygosceles Again we'll have to agree to disagree. Mathematically he does reach it "in the limit". In the limit, he reaches all the way to the tree; he doesn't come up an infinitesimal distance short. – Jeff Y Jan 31 at 20:44
1

One fallacy that is evident in your question but has not been addressed by the other answers is:

everything will occur in an infinite timeline

And you said something that is an instance of the fallacy:

if the Universe is infinite, there must be a planet exactly like ours somewhere

Both of these are completely fallacious. Nothing about an infinite process implies that it 'goes through' every possible situation. Nothing about an infinite world implies that it must have everything possible. In general, you need much more assumptions than just infinitude to conclude anything like that. Just to give you easy concrete mathematical examples to demonstrate the fallacies:

Not every positive integer occurs in the infinite sequence of odd numbers: 1, 3, 5, ...

There are infinitely many primes, but no two distinct primes have a common prime factor.

In mathematics we have a 100% precise notion of probability, and under that definition we can construct a (mathematical) probabilistic process (such as an infinite sequence of fair coin flips) in which some outcome (all heads) is possible but has zero probability. Be aware that this may not have anything to do with reality whatsoever. You need to separately think about or investigate whether some mathematical theorem can be used to deduce something about the real world. In the case of infinitely many coin flips, it says essentially nothing, because you can never in the first place flip a coin infinitely many times! If you flip a coin k times, the probability of getting all heads is 1/2^k, which is not zero. In other words, the mathematical notion of an infinite sequence of coin flips is simply impossible in reality, and the zero probability of that the all-heads outcome in the mathematical notion has zero relevance to reality.

For another example, we can construct a mathematical object corresponding to the notion of choosing a random real number uniformly from the interval [0,1]. Now consider any particular real number that is chosen in this manner. Its probability of being chosen is actually zero. Again, this is irrelevant to the real world, and does not imply that mathematics made an error ("something got chosen even though the probability of choosing it is zero"). In fact, there is no way at all in the real world to choose a real number uniformly from [0,1]! In practical applications, we can for example choose a rational number of the form k/2^32 where k seems for all practical purposes (i.e. passes all statistical tests) to be chosen randomly uniformly from the interval [0,2^32−1]. Each of these rationals would be chosen with probability 1/2^32, which is nonzero.

So be very careful in randomly interpreting very different kinds of infinite mathematical objects as saying anything about the real world.

| improve this answer | |
  • "no way at all in the real world to choose a real number uniformly from [0,1]" - I can think of a few ways, but only if it's fed into a process that only needs to use finitely many digits from it... (e.g. lazy-evaluation of less significant digits, with lazy-evaluated basic mathematical operations that output an object of the same kind, etc...) – Steve Jan 31 at 14:44
  • @Steve: That's precisely the point, isn't it? When you do what you describe, you are not choosing a random real number. Rather, you are creating a generator (in Python terminology) that outputs random digits one at a time. Nothing infinite at all. – user21820 Jan 31 at 15:41
  • Also, note that an analog random process does not give you a random real either, because you cannot extract infinite information from it. – user21820 Jan 31 at 15:42
1

If the probability of a head is 0.5 it is always 0.5, and however many times we toss a coin, there is a chance it will not be a head. This holds the same even if we keep tossing it until we get a heads. It holds for as long as we are still tossing coins, even if that's forever.

So I would then agree that the probability is not 1, and thinking otherwise is an example of the gamblers fallacy, warped through our ideas of 'infinity'.

Alternatively, an infinite number of coin tosses, or monkeys on typewriters, is not a "potential" infinity, coin tossing that does not stop, but an actual one:

Aristotle postulated that an actual infinity was impossible, because if it were possible, then something would have attained infinite magnitude, and would be "bigger than the heavens." However, he said, mathematics relating to infinity was not deprived of its applicability by this impossibility, because mathematicians did not need the infinite for their theorems, just a finite, arbitrarily large magnitude.

But I'm not sure I see how time can be an actual rather than potential infinity, in Aristotle's sense:

The actual infinite is not a process in time; it is an infinity that exists wholly at one time.

| improve this answer | |
0

The people who are pointing out that you've stumbled upon the concept of "almost sure event" in probability theory are correct, but this is rather beside the point.

The fact is that "almost sure events" (that is, events having probability 1) fail to happen all the time. Any experiment where a fair coin is tossed countably many times and a specific sequence of heads and tails is observed will have an outcome having zero probability. In other words, here is a case where we know, in advance, that there will be some event that occurs by the end of the experiment that has zero probability.

Alternatively, for instance, we can think of measuring the position of an electron occupying some energy eigenstate in a hydrogen atom. Any measurement we will make of the position of the electron has zero probability of occuring, and yet if we have a mythical apparatus capable of measuring the position exactly, then we must indeed measure some position. Again, we see clearly that an event having 0 probability doesn't mean it won't occur.

These pathologies of probability theory related to almost sure events arise from the fact that we define probability values to take real number values, and the real numbers are an Archimedean field, i.e. they don't admit any infinitesimal elements. There have been some attempts of generalizing the concept to other number systems, but none of these technical projects have any bearing on the fundamental disconnect between probabilistic claims and factual ones.

The fact is that, by design, no probabilistic claim can ever imply any claim that's not probabilistic. It's impossible, in theory, to perform a probabilistic computation (such as determining that a monkey on a typewriter will almost surely type out Shakespeare's Hamlet) and infer from this computation a fact about the world (that the monkey will indeed type out Shakespeare's Hamlet). The first is a probabilistic claim, while the second is not, and therefore it's impossible to deduce the second from the first. To perform such a deduction is indeed to fall into the gambler's fallacy, despite what some of the other answers claim. The gambler's fallacy is properly understood as the delusion that a probabilistic claim can imply a factual one, as this is the real content of a belief that "the odds will even out in the end".

The fact that, nevertheless, we seem to be able to explain some regularities in nature by using methods that are in some sense probabilistic (like using statistical mechanics to derive Planck's law of blackbody radiation, for instance) is a real conundrum that's not often appreciated. One has to think very carefully about what it is that's being done when the fundamental epiphenomenality of probability theory is somehow swept aside in what is best described as a sleight of hand. This answer is already getting rather long, however, so I will refrain from discussing this subject further.

| improve this answer | |
  • You wrote: "Any measurement we will make of the position of the electron has zero probability of occuring, and yet if we have a mythical apparatus capable of measuring the position exactly, then we must indeed measure some position." I don't agree with the first part, for much the same reason that you state "mythical apparatus" in the second part. Any measurement made by anything only gives you some numeric value with finite precision. Moreover, it doesn't even make sense to say that there is a 100% precise 'actual value' of a measurement, based on what we believe about quantum mechanics. Yes? – user21820 Jan 31 at 13:36
  • @user21820 The issue is more complicated for several reasons. Because the pictures in momentum space and position space are dual to one another under the Fourier transform (or just a unitary change of basis), it seems strange to claim that one set of eigenstates (the momentum ones) are "physical", whereas another set of eigenstates (the position ones) are not. There are also some problems with what is meant by the precision of a measurement depending on the exact nature of the apparatus used. In any event, you can get around this problem by iterating the measurement infinitely many times. – Ege Erdil Jan 31 at 14:46
  • We can't iterate a measurement infinitely many times. We can only perform each measurement once. If we 'repeat' the experiment, it is not the same experiment. About measurement, I'm just saying that any measurement device is a part of the setup, and the more precise a numeric value we can read off from it, the less accurate it can be of the underlying state in the case that the device was not there. So it's not even really sensible to talk about the probability of a measurement 'occurring'. – user21820 Jan 31 at 15:49
  • Sorry, but I think you lost me after "measuring the position of an electron" - I'm not scientifically literate enough to make sense of the analogy you've presented. – Lou Jan 31 at 15:52
  • 1
    Howerver I agree with user21820: that issue is mostly do to what we think of being a measurement. And related, what we think of being distributions. “...arise from the fact that we define probability values to take real number values” is missing the point: it's that distributions are not functions, but rather dual vectors to the space of continuous functions. In that light, the paradox can't arise, because you can't evaluate such a distribution for whether the temperature is exactly 20°. IOW, all physical measurements are inexact. – leftaroundabout Jan 31 at 16:00
0

Endless Possibilities

You are skeptical of the claim that "everything will occur, given an infinite number of opportunities." Other answers have given a good explanation of when this claim is true and when it is false. However, I would like to assemble the various ideas into a single answer.

Probability problems are often formulated in terms of choosing marbles from an opaque jar, which is valuable because it appeals to our intuition, to the extent that it can. The marbles represent the space of all possible outcomes (or: all possible values for the random variable). Picking a marble corresponds to sampling the space.

Now, there are two ways to conduct a sample: with replacement, and without replacement. After you pull out a marble, do you keep it, or do you put it back before pulling out another marble? The Gambler's Fallacy is nothing more than the mistaken idea that all probabilities (or, at least the ones of interest) entail sampling without replacement. Or, to illustrate more clearly, that all games of chance are equivalent to counting down a finite blackjack deck. If roulette involved taking each number off the wheel as it occurs, then the Gambler's Fallacy would actually be true for roulette. And if the dealer always replaced played cards into the shoe (randomly!) after every hand, it would be impossible to usefully count down a blackjack deck (it would become a circular, or "infinite" shoe, although an 8-deck shoe with a deep cut makes for a useful approximation).

Shakespearean Monkeys

When it comes to monkeys on typewriters, we have an additional complication: time. We can view the probabilistic event as a monkey striking a key, or as a monkey producing an entire sequence of keystrokes. In fact, the latter is a far more useful way to view the situation. So instead of putting a marble for each letter of the alphabet into our bag, and trying to keep track of what texts are produced by pulling out thousands of marbles, we can instead inscribe the texts which are produced by all the monkeys after 1 keystroke, after 2 keystrokes, etc. up to the limit of what monkeys are willing or able to type. So one marble will have the text "q" on it, while another will have the text "mxlplx", and yet another will have: "To be or not to be".

Since we are trying to avoid the Gambler's Fallacy, we must sample the bag with replacement. After all, there's nothing stopping a monkey from typing "MonkeyButt" 23 times in a row. So we must be able to draw this marble from the bag at least 23 times, and we can only do that if we put it back. Now, the original question becomes: "Given an unlimited number of draws, are we guaranteed that we will draw a marble with the entire text of Hamlet carefully inscribed upon its surface?" And the answer is: "It depends."

You see, we made a subtle but important leap when we switched the random variable from keys typed to texts typed. We sort of hand-waved away how long the texts could be. In fact, even if we have an infinite number of monkeys, nobody has suggested that the monkeys themselves are immortal, or have infinite patience. It could turn out that no monkey is willing to type more than 10,000 keystrokes, under any circumstances. If that is the case, then we have no chance of drawing Hamlet, no matter how lucky those keystrokes are (unless you are willing to assemble works from multiple monkeys, but that ruins the claim in other ways).

The Outer Limits

All of this is a fancy way to point out what is hopefully by now an obvious fact: you can only draw a marble from the bag, if the marble is already in the bag. If we have theoretically tireless monkeys which are highly motivated to type and physically capable of typing at least as many characters as can be found in Shakespeare, and there are no constraints on the sequences of characters typed (perhaps monkeys don't like to type 'p' after 'a' because they are on the opposite sides of a QWERTY keyboard), then, given an infinite number of "monkey texts", the probability that one of them corresponds to Hamlet is 1.

Now, let's talk about planets. If the forces which affect planet formation have a finite range, and the universe has infinite size, and the universe has infinite matter, and the universe has mostly uniform density (consistent with the observable universe, at least), and the laws of physics are the same everywhere in the universe, then we basically have the physical conditions necessary to create any kind of planet which can be formed under conditions similar to earth. Under those conditions, I would tend to agree that the probability of another earth-like planet existing is 1.

In fact, I would agree that the probability of TEN other earth-like planets is 1. I would go so far as to claim that there are an infinite number of earth-like planets in such a universe. This is due to the simple fact that we as humans can only distinguish a finite number of planets as "different", due to the limitations of physics. Therefore, we can put every "possible-planet marble" into our bag, but our bag will only contain a finite number of marbles, including our "pale blue dot". And since we will draw from the bag an infinite number of times with replacement, it follows that earth and every other kind of planet we have or will observe must occur an infinite number of times.

However, there are several things that we won't see: we won't see a cube-shaped planet, or a donut-shaped planet, or a planet that looks like a Sierpinski triangle. That's because physics does not allow the construction of such planet shapes. So an infinite number of draws does not allow anything at all to happen. It only allows any event which is individually possible to happen, possibly an infinite number of times. You can only draw a marble from the bag if the marble can exist and you put it in the bag.

| improve this answer | |
-1

You are right that infinite trials do not imply that a given state will ever be reached. The independence assumption of letters, coin tosses, and die rolls means that we are sampling with replacement. The probability that a certain sequence will never occur over infinite independent samples, while infinitesimally small, is nonzero. Thus the gambler's fallacy applies--there is actually no guarantee that a given sequence will ever occur; the present and future are not hostages to the past. Failure is an inexhaustible quantity. In sampling batches of 100 random elements each (with replacement) from a set of one million unique objects, you can be millions of batches into the sampling and it is highly likely that some elements will never have been seen, despite the total number of elements seen (including repetitions) being in the hundreds of millions. The combinatorics of sequences make the numbers involved exponentially large as the complexity of the sought sequence increases. In general there is no finite or even infinite number of trials large enough to make a guarantee that a given sequence will occur. This is a strong statement and informs our perception of what almost surely given mythic infinite resources actually means in practice.

Nuclear Wang's argument about the gambler's ruin is another important caveat: We cannot assume we have an infinite amount of any kind of resource, and some states are not recoverable, no matter how much of time and eternity we try to burn. This should color our choices with greatly warranted caution.

There are other concerns when we try to liken the monkeys-with-typewriters thought experiment to real life. For one, temporal independence is not a valid assumption in dynamical, physical systems: The present state always depends on prior states, and certain hypothetical transitions between states would be so drastic as to be impossible according to natural law. When was the last time anyone randomly teleported to the Moon, or will it ever happen? Never, and it won't. In reality, there are good reasons to believe that the probability that an organism would spontaneously generate from inorganic matter is exactly zero. Constraints such as energy wells, conservation of matter, momentum and energy, the inevitability of attraction and repulsion etc. necessarily destroy the "anything can happen" genre of fantasy. When we try to apply our discrete independent probabilistic assumptions to nature, then the natural laws, the continuity of physical reality, the smoothness of time and space and myriad other inviolable constraints all throw monkey wrenches into the monkeys-with-typewriters fiction. While a person or an animal with a well-maintained typewriter can choose to press any key at little cost and have letters appear on paper in arbitrary order, some things are truly impossible. Someone could make an interesting thought experiment by postulating a long list of things that are likely to be impossible.

I trow that no electron ever tunneled across energy barriers above a determinable finite threshold, and no electron ever will. In general, anyone who believes that any state is possible falls for the fatal trap of believing that he will be king someday, that he will escape death, that he can keep spending money he doesn't have, and that there cannot be any absolute morality because in the end, "all things are equal" and everything will happen eventually. All things are not equal. Different distributions, manifolds and the laws of nature all mandate that different choices can have permanently different outcomes. Entropy is real and active. Laws are laws, not whims. Gravity comes to work all day, every day, no exceptions. Debt and interest do not rest. Choices matter, and they determine our ultimate destination.

| improve this answer | |
  • 1
    In general there is no finite or even infinite number of trials large enough to make a guarantee that a given sequence will occur. That's mathematically false. Finite, sure. But if you go infinite, then the maths proves that if there is a non-zero probability of an event occurring, however small the probability, it will occur. And not only that, it will happen infinitely many times! This is a "smaller infinity" than the total space available, but it's still infinite. It's a bit mindbending, but that's what Georg Cantor proved. In a non-infinite universe of course this isn't the case. – Graham Feb 1 at 8:38
  • 1
    @pygosceles No, a non-zero probability over a finite time always tends to 1 as time increases. If the probability in any finite period is M (where 0<M<=1), then the probability of it occurring at least once over N periods is (1-((1-M)^N)). As N tends to infinity, P tends to 1. Nothing to do with the halting problem; that specifically covers the pathological case M=0 where things can never happen. In a finite real world of course this is not how it goes - but the OP specifically requires it to be infinite, and then your intuition-based answer breaks down. – Graham Feb 5 at 17:53
  • 1
    @pygosceles No, you're still thinking in terms of finite values. Until you can get past that, you're not going to grasp the concept. – Graham Feb 5 at 18:11
  • 1
    @pygosceles re the halting problem, it has nothing to do with "patience" - if you think it does then you haven't understood it. The point of the halting problem is purely that it's possible to construct a program such that the probability of it halting is exactly zero and that analysis of the program cannot distinguish that it is exactly zero. If the probability is exactly zero, it will never end even in infinite time which is why I said 0<M<=1 above. – Graham Feb 5 at 18:13
  • 1
    @pygosceles ... This doesn't mean that there are not programs where it can be proven that the program's probability of halting is non-zero, or proving that the program's probability of halting is zero. It only means that programs exist where this can't be proven. But this has no relevance to anything here. The probabilities can be stated, so the halting problem is a complete red herring. – Graham Feb 5 at 18:17

Not the answer you're looking for? Browse other questions tagged or ask your own question.