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

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


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.


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

Tags:

Probability