If you toss $1000$ fair coins $10$ times each, what is the probability the *some* coin will get $10$ heads?

The answer to this is supposedly close to $0.63$. However, I get approximately $0.9765625$ for the following reason:

The probability of a fair coin flipped $N$ times resulting in all heads is $1/2^N$. In this case, $1/2^{10}=1/1024$. If I flip $M$ coins, $N$ times each, there are $M$ ways for some coin to result in all heads (from the binomial coefficient "$M$ choose $1$"), so the probability of some coin resulting in all heads is $M(1/2^N)$. In this case, $1000\times 1/1024 \approx 0.9765625$.

Can someone please explain the flaw in my reasoning?

-
So if there were instead $2000$ coins, the probability would be $1.953125$? –  Chris Eagle Jan 9 '13 at 17:58
Ack, of course that makes no sense. –  user1332148 Jan 9 '13 at 18:03

4 Answers

The probability that you get no tails when you flip a fair coin $10$ times is $\left(\frac12\right)^{10}$. The probability that you get at least one tail is therefore $1-\left(\frac12\right)^{10}$. The probability that each of the $1000$ coins comes up tails at least once is then $$\left(1-\left(\frac12\right)^{10}\right)^{1000}\approx0.37642\;.$$ We want the probability of the complementary event, which is therefore about $0.62357$.

As a quick crude estimate note that $$\left(1-\left(\frac12\right)^{10}\right)^{1000}\approx\left(1-\frac1{1000}\right)^{1000}\approx\frac1e\approx0.37\;.$$

-
@Thomas: Thanks; fixed. –  Brian M. Scott Jan 9 '13 at 18:16
pure genius Brian. –  Chasky Mar 20 at 22:48

The flaw in your reasoning is that it is possible for the first coin and the tenth coin to come up all heads, in which case, your $1000/1024$ counts them both.

Essentially, $1000/1024$ is the average number (or "expected" number) of coins that will have come up all heads, but that includes the cases where more than one coin comes up heads all the time, so it doesn't work as a probability.

Consider the case where you flip two coins once each. What is the odds that one coin ended up heads? Your calculation would say, "The probability of any one coin coming up heads is $1/2$ so the probability that one of the two coins comes up heads is $2/2=1$." That is nonsensical. In this case, the probability is $3/4$.

The actual probability are $$1-\left(\frac{1023}{1024}\right)^{1000}$$

Basically, $\left(\frac{1023}{1024}\right)^{1000}$ is the odds that none of the coins are heads for all tosses.

In general, if you toss $N$ coins each $M$ times, the odds that at least one coin will have come up all heads is:

$$1-\left(1-\frac{1}{2^M}\right)^N$$

-

To calculate this, it is easier to deal with the complement, i.e. what it the probability that no coin will have 10 heads. Probability that a coin won't have 10 heads is $1-2^{-10}$, so the result to your question is $1-(1-2^{-10})^{1000} \approx 0.6235762$, the more accurate data you can find here.

-

You can also analyze this as an example of a binomial distribution, which the probability of success $p = 1/2^{10}$. The probability of none of the coins being all heads is

$$P' = \binom{1000}{0} p^0 (1-p)^{1000}$$

and the probability in question is just $P = 1 - P'$, which gives the results stated above.

-
I think this is the understanding I was trying to resurrect after all these years: $$P = \binom{n}{k} p^k q^{n-k}$$ This, and the utility of the complement. –  user1332148 Jan 9 '13 at 19:46