21

I'm reading The Master Algorithm by Pedro Domingos and I'm having a hard time understanding something he wrote on page 74:

"If you do a million runs of a thousand coin flips, it's practically certain that at least one run will come up all heads."

My intuition tells me this is false. My understanding of probability would indicate that the chance of encountering $1000$ heads in a row after trying $1000000$ times is:

$$\frac{1}{2^{1000}} *1000000$$

which is minuscule and hardly "practically certain." Is my understanding correct, or am I missing something?

  • 12
    Unless by "millions", the author means on the order of 2^1000 millions, the author is wrong, and your intuitive estimate, though not exactly right, is still approximately correct. One million runs of the test will still yield a probability of near zero. – quasi Jun 03 '17 at 17:22
  • Try reading on the geometric distribution, it seems related. – Sean Roberson Jun 03 '17 at 17:23
  • 4
    The expected number of runs to get all heads is $2^{1000}$ – kludg Jun 03 '17 at 18:03
  • 2
    Although your intuition is correct, your math is not correct. If the formula for determining this was as simple as 1/(2^x) * y, then by the same logic, if I flipped a coin twice, 1/2*2 = 100% chance I would get a heads (when the real probability is 75%) – moonkey69420 Jun 04 '17 at 02:35
  • 1
    The book's author doesn't say "million" but simply "more and more". At least it is so in the copy of the book in my hand right now. – Geoff Jun 04 '17 at 12:24
  • @Geoff - $2^{1000}$ is so huge number that you can safely say "if you toss 1000 fair coins, you never get 1000 heads". Some books compare it with the lifetime of universe, like that "suppose you are tossing 1000 coins every second since the Big Bang, and still the probability of getting 1000 heads is negligible, consequently it never happens" – kludg Jun 04 '17 at 13:38
  • "If you do a million runs of 20 coin flips, it's pretty likely that at least one run will come up all heads" is a correct statement. For it to be "practically certain", you'd want to go far lower, maybe runs of ten flips. – Eric Lippert Jun 04 '17 at 20:47

6 Answers6

19

Yes, the author is incorrect. The probability that at least one run is all heads is $$ 1-(1-2^{-1000})^{10^6} $$ However, $2^{1000}$ is extremely large. Indeed, since $2^{10}=1024>1000=10^3$, we have $2^{1000}>10^{300}$, so by Bernoulli's inequality $$ (1-2^{-1000})^{10^6}\geq 1-\frac{10^6}{2^{1000}}>1-\frac{10^{6}}{10^{300}}$$ and so $$ 1-(1-2^{-1000})^{10^6}<\frac{10^6}{10^{300}}=10^{-294}$$

carmichael561
  • 53,688
4

The chances that flipping 1000 coins gives all heads is given by $\frac{1}{2^{1000}}$ as you predicted. However, the odds that this will happen, given that you try it $1000000$ times is: $$1 - \left(1 - \frac{1}{2^{1000}}\right)^{1000000}$$ The certainty of which, I'm not too sure about. My calculator can't seem to handle it.

EDIT: Seems like the probability is still negligible. Author is wrong on this account. However, the point being made is that adding on extra trials causes an exponential growth of probability, making impossible things happen if you're willing to run enough trials.

Kaynex
  • 2,448
  • 1
    No, it's close to zero. If the exponent was $2^{1000}$, it would be close to $1-1/e$. – quasi Jun 03 '17 at 17:25
  • Good point, I forgot about that rule. Shame, because this would be a cool fact otherwise. – Kaynex Jun 03 '17 at 17:27
  • And while $10^6$ trials is doable, $2^{1000}$ trials, while theoretically doable, is not real-world doable. – quasi Jun 03 '17 at 17:31
  • You can use the rule $(1+ a)^n = 1 +an$ for small $a$ –  Jun 03 '17 at 17:32
  • 5
    We have $$ 1-(1-2^{-1000})^{10^6} = f^{-1}(10^6 f(2^{-1000})) $$ where $f(x)=\log(1-x)$. The Taylor series for $f$ and its inverse are well known. Using them with just two terms -- $f(x)=0-1x+o(x)$ -- gives simply $10^6\cdot 2^{-1000}$ and the error bound that this differs from the true value by at most about the square of the true result -- so the OP's simple calculation actually gives us a ridiculously good approximation to the probability in this particular case. – hmakholm left over Monica Jun 03 '17 at 18:00
  • Get a better calculator. – richard1941 Jun 11 '17 at 01:50
4

For another perspective on why OP's heuristic estimate is so spot-on:

The number of successes on $n = 10^6$ trials where the probability of a success is $p = \frac{1}{2^{1000}}$ is well-approximated by a Poisson distribution with parameter $$\lambda = np = \frac{10^6}{2^{1000}}.$$

In a Poisson distribution the probability that there is at least 1 occurrence is $1 - e^{-\lambda}$. But $$1 - e^{-\lambda} \approx \lambda$$ for $\lambda \approx 0$, hence the probability is approximately $\lambda = \frac{10^6}{2^{1000}}$.

John Coleman
  • 5,401
2

This is absolutely false. As others point out, the probability of this happening is $1-(1-2^{-1000})^{10^6}$ which is tiny. The author is either wrong, or the OP misunderstood.
For some sense of scale, I present the following math:

$$ \begin{align} (1-2^{-1000})^{10^6} &= (1-n)^a \\&=\exp[a\log (1-n)] \\&\approx\exp\left[a\left(-n-\frac{n^2}{2}+O(n^3)\right)\right] \\&= \exp\left[-an-\frac{an^2}{2}+O(n^3)\right] \\&\approx 1-an-\frac{an^2}{2}+O(n^3)+\frac{1}{2}\left(-an-\frac{an^2}{2}+O(n^3)\right)^2+O(n^3) \\&= 1-an\left[1+\frac{n}{2}(1+a)\right]+O(n^3) \end{align}$$ Accordingly, we have that $$\begin{align} 1-(1-2^{-1000})^{10^6} &\approx 10^62^{-1000}\left[1+2^{-1001}(1+10^6)\right] \\&= 10^62^{-1000}\left[1+2^{-1001}10^6+2^{-1001}\right] \\&= 10^6 2^{-1000}+ 2^{-2001}(10^{12}+10^6) \end{align}$$ Clearly this second term is much smaller than the first term (interestingly, if we remove it, we retrieve the OP's estimation!) The error is $O(n^3)$, so this approximation should be quite good!

Brevan Ellefsen
  • 14,793
1

The number you computed is the expected number of successes: $$ 10^6\cdot2^{-1000}\lt10^{-295} $$ The probability of at least one success is $$ 1-\left(1-2^{-1000}\right)^{10^6} $$ which, by the Binomial Theorem, is a little less: $$ 10^6\cdot2^{-1000}-\binom{10^6}2\cdot2^{-2000}+\binom{10^6}3\cdot2^{-3000}-\cdots $$ where $\binom{10^6}2\cdot2^{-200}\lt10^{-590}$ and $\binom{10^6}3\cdot2^{-300}\lt10^{-885}$. Thus, both the expected number and the probability are less than $10^{-295}$.

robjohn
  • 345,667
0

Multiply a trillion times a trillion 25 times. This number of trials is enough to give a reasonable chance to throw 1,000 heads in a row. No computer or human is capable of performing this many trials, even if it started at the "big bang" beginning of the universe and managed to perform a trillion trials every second. Substituting "more and more" for "million" does not fix the error. There is no reasonable chance under any realistic scenario that 1,000 heads can be flipped in sequence. The effective probability is zero.

theBillyLeePontificator.com
  • 1