21
$\begingroup$

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?

|cite|improve this question
$\endgroup$
  • 12
    $\begingroup$ 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. $\endgroup$ – quasi Jun 3 '17 at 17:22
  • $\begingroup$ Try reading on the geometric distribution, it seems related. $\endgroup$ – Sean Roberson Jun 3 '17 at 17:23
  • 4
    $\begingroup$ The expected number of runs to get all heads is $2^{1000}$ $\endgroup$ – kludg Jun 3 '17 at 18:03
  • 2
    $\begingroup$ 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%) $\endgroup$ – DaemonOfTheWest Jun 4 '17 at 2:35
  • 1
    $\begingroup$ 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. $\endgroup$ – Geoff Jun 4 '17 at 12:24
20
$\begingroup$

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}$$

|cite|improve this answer
$\endgroup$
  • 5
    $\begingroup$ However $1-(1-2^{-1000})^{10^6}$ is quite well approximated by $10^6\cdot 2^{-1000}$, so I think calling the askers's calculation "incorrect" is a bit of a stretch. "Not exact" is really the worst thing one could call it. $\endgroup$ – hmakholm left over Monica Jun 3 '17 at 17:32
  • 2
    $\begingroup$ @HenningMakholm: the author says it's "practically certain" that at least one run is all heads when in fact the opposite is true. I think incorrect is a fair word to use. $\endgroup$ – carmichael561 Jun 3 '17 at 17:33
  • 2
    $\begingroup$ Whoops, typo. It was the asker's calculation I objected to calling "incorrect". $\endgroup$ – hmakholm left over Monica Jun 3 '17 at 17:34
  • $\begingroup$ Ah, I see. I will edit my first sentence. $\endgroup$ – carmichael561 Jun 3 '17 at 17:35
6
$\begingroup$

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}}$.

|cite|improve this answer
$\endgroup$
5
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • 1
    $\begingroup$ No, it's close to zero. If the exponent was $2^{1000}$, it would be close to $1-1/e$. $\endgroup$ – quasi Jun 3 '17 at 17:25
  • $\begingroup$ Good point, I forgot about that rule. Shame, because this would be a cool fact otherwise. $\endgroup$ – Kaynex Jun 3 '17 at 17:27
  • $\begingroup$ And while $10^6$ trials is doable, $2^{1000}$ trials, while theoretically doable, is not real-world doable. $\endgroup$ – quasi Jun 3 '17 at 17:31
  • $\begingroup$ You can use the rule $(1+ a)^n = 1 +an$ for small $a$ $\endgroup$ – user370967 Jun 3 '17 at 17:32
  • 5
    $\begingroup$ 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. $\endgroup$ – hmakholm left over Monica Jun 3 '17 at 18:00
2
$\begingroup$

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!

|cite|improve this answer
$\endgroup$
1
$\begingroup$

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}$.

|cite|improve this answer
$\endgroup$
0
$\begingroup$

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.

|cite|improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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