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?

Solution 1:

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

Solution 2:

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.

Solution 3:

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

Solution 4:

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!

Solution 5:

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