probability

Uncanny Coincidences

Many years ago I dreamt of a reptile, a komodo dragon like creature. The following day while walking through a mall I stopped dead in my tracks when I saw a sculpture of that very animal in my dream. Back then the experience blew my mind.

Eerie coincidences like this are usually memmorable and because we ascribe mystical properties to dreams we tend to invest them with meaning (hidden or otherwise). The fact is, however, our innumeracy of probability theory has gotten the better of us. Coincidences, however uncanny, are to be expected and how often or how much we should expect them can be derived with precision.

Take the simplest example: coin tosses. We know that sometimes we get a run of 2, 3, 5, and even more, of heads or tails. Nothing particularly extraordinary about that. But what about getting 100 tails or heads in a row? Assuming the coin is fair/unbiased wouldn't that take a miracle? Let's find out.

Let's begin at the beginning. How many times do we have to flip a coin to achieve a 50% chance of getting at least one heads (yes, Virginia, that's spelled with an s)? The probability of getting heads on a coin toss is 50% so we need only toss it once.

Let's move up one notch. How many times do we have to flip a coin to achieve a 50% probability of getting two heads in a row at least once? If we flip a coin twice, the probability of getting heads on both tries is (0.5)(0.5) = 0.25. Therefore, the probability of not getting two heads = 1 - 0.25 = 0.75. If we flip the coin three times, the probability of not getting two heads on the first and second flips is as we've seen 0.75. Likewise the probability of not getting two heads on the second and third flips is also 0.75. Therefore, the probability of not getting two heads in a row in three coin flips is (0.75)(0.75) = 0.5625. With four tosses the probability of not getting any pair of heads in a row is (0.75)(0.75)(0.75) = 0.421875. And so the probability of having at least one pair of heads in a row in four flips = 1 - 0.421875 = 0.578125 or around 58%. Thus we need to toss a coin 4 times to achieve a 50% chance of getting two heads in a row at least once.

What about a run of 10 heads? We begin again with the minimum number of coin flips. In this case it's ten. The probability of getting 10 heads in a row = 0.5¹⁰ = 0.0009765625. And so the probability of not getting 10 heads in a row is its complement or 1 - 0.0009765625 = 0.9990234375. Keep in mind we've flipped the coin ten times. On the 11th flip the probability of 10 heads in a row is the probability of getting ten heads on the 2nd to 11th flip. On the 12th flip we're looking for the probability of getting ten heads on the 3rd to 12th flip. And so on. Therefore after having tossed the coin 11 times the probability of not getting ten heads in a row is the probability of not getting ten heads in a row on the 1st to 10th flip multiplied by the probability of not getting ten heads on the 2nd to 11th flip. That's 0.9990234375². And on the 12th flip the probability = 0.9990234375³. Take note and remember the exponent in the equation vis-a-vis the number of coin flips actually made. It's an important distinction.

If, after initially flipping the coin nine times, we toss it a hundred times more the probability of NOT getting 10 heads in a row = 0.9990234375¹⁰⁰. Therefore the probability of getting tens heads in a row at least once = 1 - 0.9990234375¹⁰⁰ = .0923 approximately. That's less than 10%. What if we flip the coin 1000 times instead of 100? The probability then becomes 1 - 0.9990234375¹⁰⁰⁰, which comes out to around 62%. So to achieve a 50% chance of getting 10 heads in a row at least once we'd need to flip a coin somewhere between 100 to 1000 times. But what is it exactly? Is it 500 times? 972? Is there a way to nail that number other than looking for it by trial and error? Well, I'm glad you asked.

Let:
x = number of heads in a row we're interested in
p = chances/probability of getting x heads in a row at least once
f = coin flips necessary to achieve p

Actually f isn't really the exact number of flips we need to achieve p, as we saw above in the ten heads example. There's an initial setup where we need to flip the coin x - 1 times. So in the case of a run of ten heads we said we had to flip the coin 9 times. And then on the tenth flip (that's when f = 1) we can begin computing for the probability of having x heads in a row.

Let
F = exact number of coin flips necessary to achieve p

Because of the necessary "initial setup" of x - 1 flips we obtain
F = f + x - 1

As we've seen above:

Probability of getting x heads in a row = 0.5^x
Probability of not getting x heads in a row = 1 - 0.5^x
p = 1 - (1 - 0.5^x)^f

Solving for f we obtain:

(1 - 0.5^x)^f = 1 - p
log [(1 - 0.5^x)^f] = log(1 - p)
(f)log (1 - 0.5^x) = log(1 - p)
f = log(1 - p) / log [(1 - 0.5^x)

Let's take that formula out for a test run and see what we get.

Instead of p = 50%, let's see how many times we need to toss a coin when p = 99.9% --very close to near certainty of getting x heads in a row at least once. Applying the same equations we obtain the following values.

So getting a run of 100 heads is quite possible. And getting 1000 in a row is theoretically achievable--if we can flip coins fast enough before the universe runs out of gas. Perhaps someone's already doing a simulation on a computer.

Notes:

Instead of an experiment with an initial x-1 flips and then adding one new toss and getting the probability of the last x tosses, we can do one set of x number of coin flips, and then do another set of x flips, and then another set, and so on. In such a case f is the number of sets of x flips and therefore the total number of actual coin flips is (f)(x). Example: for x = 10 and f = 7000, F = 7000 (10) = 70,000. The equation for f remains the same. We just end up with a larger number of coin tosses.

If you take a look at the values of x and F in the tables, you'll notice a trend. Whenever x is incremented by 10 (i.e., x + 10), F increases by three orders of magnitude. In fact F increases by 1024 or 2¹⁰. As you can see that exponent is equal to the difference in the values of x. Thus, if we increase x from 20 to 50 F will increase by a factor of 2³⁰ since 50 - 20 = 30. Let's write out the formula for F in terms of the difference in values of x.

Let
x_i >= 10
x_n > x_i
f_xn = f given x = x_n
f_xi = f given x = x_i

for a particular p, f_xn = (2^{(x_n - x_i)})(f_xi)

Example:
x_i = 100
x_n = 500
From the table where p = 99.9% we find that for x = 100, f = 8.76 x 10³⁰
Therefore, for x = 500
f = (2^{(500 - 100}))(8.76 x 10³⁰) = 2.26 x 10¹⁵¹