What's the probability of getting 1000 heads in a row?

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?

• 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. Jun 3, 2017 at 17:22
• Try reading on the geometric distribution, it seems related. Jun 3, 2017 at 17:23
• The expected number of runs to get all heads is $2^{1000}$ Jun 3, 2017 at 18:03
• 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%) Jun 4, 2017 at 2:35
• 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. Jun 4, 2017 at 12:24

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

• 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. Jun 3, 2017 at 17:32
• @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. Jun 3, 2017 at 17:33
• Whoops, typo. It was the asker's calculation I objected to calling "incorrect". Jun 3, 2017 at 17:34
• Ah, I see. I will edit my first sentence. Jun 3, 2017 at 17:35

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.

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

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

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!

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

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.