# probability

March 2016

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

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.9990234375100. Therefore the probability of getting tens heads in a row at least once = 1 - 0.9990234375100 = .0923 approximately. That's less than 10%. What if we flip the coin 1000 times instead of 100? The probability then becomes 1 - 0.99902343751000, 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.5x
Probability of not getting x heads in a row = 1 - 0.5x
p = 1 - (1 - 0.5x)f

Solving for f we obtain:

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

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

p = 50%
x f (rounded up) F (rounded up)
1 1 1
2 3 4
3 6 8
4 11 14
5 22 26
10 710 719
20 726,818 726,837
30 744,261,118 744,261,147
40 762,123,384,786 762,123,384,825
50 780,414,346,020,669 780,414,346,020,718
100 ≈ 8.79 x 1029 ≈ 8.79 x 1029

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.

p = 99.9%
x f (rounded up) F (rounded up)
1 10 10
2 25 26
3 52 54
4 108 111
5 218 222
10 7,071 7,080
20 7,243,303 7,243,322
30 7,417,145,750 7,417,145,779
40 7,595,157,251,069 7,595,157,251,108
50 7,777,441,025,097,630 7,777,441,025,097,680
100 ≈ 8.76 x 1030 ≈ 8.76 x 1030
1000 ≈ 7.4 x 10301 ≈ 7.4 x 10301

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 210. 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 230 since 50 - 20 = 30. Let's write out the formula for F in terms of the difference in values of x.

Let
xi >= 10
xn > xi
fxn = f given x = xn
fxi = f given x = xi

for a particular p, fxn = (2(xn - xi))(fxi)

Example:
xi = 100
xn = 500
From the table where p = 99.9% we find that for x = 100, f = 8.76 x 1030
Therefore, for x = 500
f = (2(500 - 100))(8.76 x 1030) = 2.26 x 10151