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?

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.
