{"id":92,"date":"2008-07-19T01:07:21","date_gmt":"2008-07-19T06:07:21","guid":{"rendered":"http:\/\/www.moroha.net\/blog\/?p=92"},"modified":"2012-04-17T13:17:06","modified_gmt":"2012-04-17T18:17:06","slug":"how-to-get-92-heads-in-a-row","status":"publish","type":"post","link":"https:\/\/www.moroha.net\/blog\/archives\/92","title":{"rendered":"How to get 92 heads in a row"},"content":{"rendered":"

A couple of posts<\/a> ago I talked about how laughably improbable it would be to get 92 heads in a row on a fair coin. To sum up, the probability is:
\n

\\(\\displaystyle\\left(\\frac{1}{2}\\right)\\left(\\frac{1}{2}\\right)\\left(\\frac{1}{2}\\right)\\cdots\\left[\\text{92 times}\\right]\\cdots\\left(\\frac{1}{2}\\right)=2^{-92}=2.017\\times 10^{-28}\\)<\/center><\/p>\n

The probability of this happening is so abysmally low that you could flip coins your entire life and never expect to see this happen. Or could you? How many times would<\/em> you need to flip a coin to see a reasonable chance of this happening?<\/p>\n

A pointless question? Most certainly. But trying to answer pointless questions that can be solved by math is one of the trademarks of a geek. So a quick review of probability and statistics lead me to the Geometric Distribution<\/a>, which gives the probability of an event occurring after a given number of trials.
\n

\\(\\displaystyle{P=p\\left( 1-p\\right)^{k-1}}\\)<\/center>
\nHere p<\/em> is the probability of the event occurring once in one trial, i.e. \\(2.017\\times 10^{-28}\\). k<\/em> is the number of trials, and P<\/em> is the probability of the event occurring once within k<\/em> trials. However, this equation doesn’t quite give us the probability distribution we need. This function will give us the probability of getting exactly one event (heads 92 times in a row) out of k<\/em> trials (flipping a coin 92 times in a row k<\/em> times). We’re not interested in the probability of exactly one success, we’re interested in the probability of one or more<\/em> successes. For that, we need the related Cumulative Distribution Function. Basically it’s the sum of the probabilities of 1, 2, 3,… up to k<\/em> successes out of k<\/em> trials. It’s actually pretty easy to derive without performing sums for arbitrarily large values of k<\/em>. Since we want one or more successes, that means the only thing we don’t want is a failure for every<\/em> trial. The probability of a single failure is simply \\(1-p\\), so the probability of k<\/em> failures is \\(\\left( 1-p\\right)^{k}\\). Since we want every possible combination except every trial a failure, we just subtract this from 1 (the sum of all<\/em> possible combinations is of course equal to one). This function comes out to be:
\n
\\(\\displaystyle{F=1- \\left( 1-p \\right)^k}\\)<\/center>
\nChoosing a reasonable number for F<\/em>, we’ll select 0.98. Solving the above equation for k<\/em> we get:
\n
\\(\\displaystyle{k=\\frac{\\text{ln}\\left( 1-F\\right)}{\\text{ln}\\left( 1-p\\right)}}\\)<\/center><\/p>\n

This equation is exact, but it has a big problem. No normal calculator or computer is going to be able to calculate the answer because of the denominator. The logarithm of one is zero, so the logarithm of a number very very close to one is a very very small number. But no normal calculator is going to be able to handle \\(\\text{ln}\\left( 1-2^{-92}\\right)\\approx\\text{ln}\\left( 0.999999999999999999999999999798\\right)\\)
\n(Note I said no normal<\/em> calculator. I used Mathematica<\/a> for this and it works fine. But anything limited to double-precision arithmetic isn’t going to get you there.) Fortunately there is a convenient Taylor series expansion for \\(\\text{ln}\\left( 1-x\\right)\\). It is
\n

\\(\\displaystyle{\\text{ln}\\left( 1-x\\right)=\\sum_{i=1}^{\\infty}\\frac{x^i}{i}}\\)<\/center>
\nThe first term in the series will give more than sufficient precision in this case, so we have
\n
\\(\\displaystyle{k=-\\frac{\\text{ln}\\left( 1-F\\right)}{p}}\\)<\/center>
\nThis tells us how many trials we we will need to to have a 98% confidence of getting 92 heads in a row, but it doesn’t tell us how many coin flips we will need. Now a trial is defined as 92 coin flips, and if all 92 are heads it is a success, otherwise it is a failure. However, we don’t need to do all 92 flips each time, as soon as we get our first tails, we already know that the trial is a failure and we can start over. Since a fair coin is going to result in tails half of the time, then that means on average we will have two flips for every trial. So if f<\/em> is the total number of coin flips we will need to get a 98% confidence, then:
\n
\\(\\displaystyle{f=-\\frac{2\\;\\text{ln}\\left( 1-0.98\\right)}{2^{-92}}=3.874\\times 10^{28}}\\)<\/center>
\nThis is a very very big number. If we flipped a coin once a second, how long would it take us to get this number of flips?
\n
\\(\\displaystyle{3.874\\times 10^{28}\\,\\text{flips}\\left( \\frac{1\\;\\text{s}}{1\\;\\text{flip}}\\right)\\left( \\frac{1\\;\\text{yr}}{3.1557\\times 10^{7}\\;\\text{s}}\\right)=1.22\\times 10^{21}\\;\\text{yr}}\\)<\/center>
\nAnd how long is this? This is really, really<\/em> long. Astronomers estimate the current age of the universe to be \\(1.373\\times 10^{10}\\) years old. That puts it as 100 billion times longer than the current age of the universe. This is a feat that could only be pulled off by, say, Wowbagger, the Infinitely Prolonged<\/a>. According to this fascinating article<\/a> on the eventual heat death of the universe, at this point there will be no matter left in the universe but white and black dwarfs (and black holes, but I don’t know if they’re considered to be matter within our universe or not), and they will be flung from their orbits due to gravitational radiation.<\/p>\n

So is all lost? Is there no way to get 92 heads in a row? For all practical purposes, yes, there is no way. As for impractical<\/em> purposes though, in a subsequent post I’ll detail a way that we could accomplish it long before the death of the universe using a scheme that in all reality would only make sense in a Douglas Adams’ universe.<\/p>\n","protected":false},"excerpt":{"rendered":"

A couple of posts ago I talked about how laughably improbable it would be to get 92 heads in a row on a fair coin. To sum up, the probability is: The probability of this happening is so abysmally low … Continue reading →<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[2],"tags":[],"_links":{"self":[{"href":"https:\/\/www.moroha.net\/blog\/wp-json\/wp\/v2\/posts\/92"}],"collection":[{"href":"https:\/\/www.moroha.net\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.moroha.net\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.moroha.net\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.moroha.net\/blog\/wp-json\/wp\/v2\/comments?post=92"}],"version-history":[{"count":27,"href":"https:\/\/www.moroha.net\/blog\/wp-json\/wp\/v2\/posts\/92\/revisions"}],"predecessor-version":[{"id":591,"href":"https:\/\/www.moroha.net\/blog\/wp-json\/wp\/v2\/posts\/92\/revisions\/591"}],"wp:attachment":[{"href":"https:\/\/www.moroha.net\/blog\/wp-json\/wp\/v2\/media?parent=92"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.moroha.net\/blog\/wp-json\/wp\/v2\/categories?post=92"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.moroha.net\/blog\/wp-json\/wp\/v2\/tags?post=92"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}