Probability for having consecutive success in an experiment

Question

A friend asked me the following question:

"In an experiment, we are tossing a fair coin 200 times. We say that a coin flip was a success if it's heads. What is the chance for having at least 6 consecutive successes?"

And according to him, the answer is nearly 100%.

My calculations were different. I'd like to know if I am mistaken or he is.

What I did:

I noticed that if we have 6 consecutive successes, then the first success in our winning streak can be anywhere from the first experiment to the 194'th experiment.

So when you think about it, we can have first 6 coin flips successful, and then whatever. or we can have first flip failure, and then 6 successes, and then whatever, or we can have 2 failures and then 6 successes and then whatever, and so on.

When you sum it all up, it looks like $S=(\frac{1}{2})^6+\frac{1}{2}*(\frac{1}{2})^6+(\frac{1}{2})^2*(\frac{1}{2})^6+...+(\frac{1}{2})^{193}*(\frac{1}{2})^6$

This is a geometric series, with $a_1=(\frac{1}{2})^6$, $n=194$, $q=\frac{1}{2}$.

Using the well known formula $S_n=\frac{a_1(q^n-1)}{q-1}$ I get that in our case $S_{194}=\frac{1}{32}$.

Was I mistaken somewhere? not really close to the 100% mark. Or is my friend mistaken.

Edit: I just realized my mistake. It's possible for example to have first one success, second one failure, and then 6 successes. I didn't take that into account. So my calculation is wrong. So how do I calculate this?

Answer 1

Your evaluation is wrong in that, for example, if the third term is supposed to represent the probability of having the first "run" (6 consecutive heads) starting on coin 3, then you are assuming that the first two coins are tails, but that's not necessary (it could also be H T H H H H H H).

The correct derivation is not so simple. This problem has been asked (with variations) several times here. See for example here and linked question.

In Octave/Matlab:

> M=[ 1 1 0 0 0 0 0;
>     1 0 1 0 0 0 0;
>     1 0 0 1 0 0 0;
>     1 0 0 0 1 0 0;
>     1 0 0 0 0 1 0;
>     1 0 0 0 0 0 1;
>     0 0 0 0 0 0 2] /2 ;
> p=[1 0 0 0 0 0 0] * M^200 *[0 0 0 0 0 0 1]'
p =  0.80093

The simple approximation explained in the link above gives: $p\approx 1-(1-1/32)^{50}=0.79555\cdots$

Both agree in a probability of about 80%.

Answer 2

Feller, "An Introduction to Probability Theory and Its Applications", Third Edition, gives a useful approximation on p. 325, equation 7.11.

Suppose we toss a possibly biased coin $n$ times, where the probability of a head is $p$ and $q = 1-p$. Let $q_n$ be the probability there is no run of $r$ successive heads. Then

$$q_n \sim \frac{1-px}{(r+1-rx)q} \cdot \frac{1}{x^{n+1}} $$

where $x$ is the smallest positive root of $1 - x + q p^r x^{r+1} = 0$.

For your problem, $p = q = 1/2$, $r = 6$, $n= 200$, and we find $x \approx 1.008276517$, so $q_n \approx 0.19906$ and $1-q_n$, the probability that there will be a run of at least 6 heads, is about $0.80093$.