# Probability of flipping 10,000 coins and getting at least one 10 consecutive heads?

I know that the probability of getting 10 consecutive heads is (0.5)ˆ10 = 0.0009765625. However, I don't know how to get the probability of getting at least one 10 consecutive heads out of 10,000 independent coins (flipping 10 times for each coin)

Thank you for all the help

• So to clarify, you're flipping $10,000$ coins $10$ times each, and you want the probability that at least one of these coins gets all heads? – carmichael561 Apr 5 '17 at 22:32
• As another framing, you are flip a coin 10 times, and coin and count the trial as a success if you get 10 heads. You repeat this 10,000 times, and you want to know the probability of getting at least one success. Is that what you are asking? If so, the probability comes out to $1-(1-2^{-10})^{10000}$. – Kajelad Apr 5 '17 at 22:54

Using the formula shown at MathWorld: $$R_p(r,n) = \sum_{i=r}^n c_i^p, \\ F_p(r,s) = \frac{p^r s^r (1-p s) }{1-s + (1-p) p^r s^{r+1}} = \sum_{i=r}^\infty c_i^p s^i,$$ for the choices $p = 1/2$, $r = 10$, $n = 10^4$, using Mathematica, I get the probability $$0.99258389438655053993775098855095821370491145810634378756681285501319 7695\ldots.$$

This can also be expressed as $$1 - \frac{F_{10^4+2}^{(10)}}{2^{10^4}},$$ and in general, for $n$ fair coin tosses, the probability of at least one run of $r$ consecutive heads is $$1 - \frac{F_{n+2}^{(r)}}{2^n},$$ where $F_n^{(r)}$ is a Fibonacci $r$-step number satisfying the recursion relation $$F_n^{(r)} = \begin{cases} 0, & n \le 0, \\ \sum_{i=1}^{r} F_{n-i}^{(r)}, & n \ge 1, \end{cases}$$ of which the familiar Fibonacci sequence corresponds to $r = 2$. This in turn can be written as $$1 - \frac{1}{2^n} \left[\frac{\rho^{n+1} (\rho - 1)}{(r+1)\rho - 2r}\right],$$ where $[ \cdot ]$ represents the nearest integer function, and $\rho > 1$ is the nontrivial positive root of $$\rho^{r+1} - 2\rho^r + 1 = 0.$$ In your case, $r = 10$ gives $$\rho \approx 1.9990186327101011386634092391291528618543100760622.$$

A crude approximation using a Poisson distribution is possible. We note that for a fair coin the probability of 10 consecutive heads is $\lambda = 1/1024$. This is our "rare event" rate parameter. Then if we treat the coin tosses as a Poisson process, we see that the probability that at least one event occurs in $10^4$ observations (ignoring the dependence) is $$\Pr[N \ge 1] = 1 - \Pr[N = 0] = 1 - e^{-10^4/1024} \approx 0.999943.$$ This overestimates the true probability because as we know, sequences of 10 tosses are not independent.

Well, one way to approach it is to start with $f(x,n)$ being the number of successful combinations in which $x$ consecutive heads appear in $n$ flips and an attempt to find $f(x,n+1)$. If we have $f(x,n)$ adding another coin flip will increase the total number of successful combinations in two ways. It doubles the successful combinations in the previous arrangement in addition to adding new successful combinations. A new successful combination can only be added when the last $n+1-x$ coins are heads and the $n-x$ coin is a tail. Moreover, we must subtract the number of successful arrangements within the first set of $n-x$ coins. In summary, this gives you the recursion formula:

$f(x,n+1) = 2f(x,n) + (2^{n-x}-f(x,n-x))$

Converting this into probabilities

$p(x,n+1) = p(x,n) + (2^{-(x+1)} - p(x,n-x)2^{-(x+1)})$

so

$p(x,n+1) = p(x,n) + (1 - p(x,n-x))2^{-(x+1)}$

but if $2x>n$, $p(x,n-x)$ is $0$, then solving the recursion formula is easy as it's linear in $n$ and we know $p(x,x) = 2^{-x}$.

for $3x>n$, we must apply the recursion formula to $p(n,n-x)$ as well, which makes the formula a quadratic in $n$ that is (not so easy) to find. In this case $101x>n$ so the probability is the output of some ghastly 100 order polynomial. Needless to say, this method sacrifices pretty much all computational usefulness for the sake of generality. I mean, who wants to flip 500 or 300 heads in a row? I just thought it would be interesting

• finding the expected value of flips needed is a much easier problem actually, and you can estimate a probability from that – Dis-integrating Aug 6 '17 at 10:58

Here is an attempt at a solution: Let the probability of getting at least one string of $M$ consecutive heads in a total of $n$ tosses be $p_{n}$. Clearly $p_{n} =0$ if $n<M$ and $p_{M} = 2^{-M}$. For $n \geq M$, we have
\begin{align} p_{n} &= 2^{-1}p_{n-1}\mathbb{1}_{n-1 \geq M} + 2^{-2}p_{n-2}\mathbb{1}_{n-2 \geq M} + \ldots+2^{-M}p_{n-M}\mathbb{1}_{n-M \geq M} + 2^{-M}\mathbb{1}_{n \geq M}\\ &= 2^{-M}\mathbb{1}_{n \geq M}+\sum_{j=1}^M 2^{-j}p_{n-j}\mathbb{1}_{n-j \geq M} \end{align}

Can't think of an easy way to solve it, but defining $q_{n} = 2^n p_{n} \mathbb{1}_{n\geq M}$, to rewrite the above recurrence as $$q_{n} = q_{n-1} +q_{n-2}+\ldots+q_{n-M} + 2^{n-M}\mathbb{1}_{n \geq M}$$ might help.... Note that in the question posed $M=10, n= 10000$.