# Probability of a run of heads of length at least $2$ when flipping a coin $n$ times.

There are $2^n$ equally likely outcomes when flipping a fair coing $n$ times. The probability in question can be written: $$p_{2,n}=\frac{R(2,n)}{2^n}$$ Where the numerator, $R(2,n)$ counts the number of sequences of $n$ flips of a fair coin where there is at least one run of heads of length at least $2$.

My approach: Count the number of sequences without a run of length at least $2$ and subtract from $2^n$. I have split the counting job into two cases:

$n$ odd: Start with the case where we have alternating heads and tails throughout which we write as: $$HTHTHT...HTH$$ or $$THTHTH...THT$$ We have the two cases here where the sequence starts (and ends) with $H$ or $T$.

For each of these starting positions, each $H$ can remain an $H$ or "morph" into a $T$ and so we have $2^{\lfloor{\frac{n+1}{2}}\rfloor}$ and $2^{\lfloor{\frac{n}{2}}\rfloor}$ for the first and second cases above respectively. Also, we count the case where all flips are $T$ twice here so finally we must add $1$. And this is it so for $n$ odd we get: $$R(2,n) = 2^n - 2^{\lfloor{\frac{n+1}{2}}\rfloor} - 2^{\lfloor{\frac{n}{2}}\rfloor}+1$$

$n$ even: Again we have two cases: $$HTHTHT...HT$$ and $$THTHTH...TH$$ and by the same logic as above we have in each case, $2^{\frac{n}{2}}$ sequences without the run we are looking for. Again we count the case where all flips are $T$ twice again so we must subtract it out but we are missing the case where the first and last flip are $H$ and the rest are $T$ so in total we adjust our count by $0$ giving for $n$ even: $$R(2,n) = 2^n - 2^{\frac{n}{2}+1}$$.

My question: I have doubts about this derivation. Even if it is correct I would be interested in a formula for all $n$ since I think splitting it into cases depending on parity is "messy". Anyone know of any corrections/improvements or other proofs/formulas? Thanks.

-
With this reasoning, you won't count all sequences. For example: THHT... – barto Sep 11 '13 at 18:31

Hint: Your basic strategy is right. We count the number of strings of length $n$ with no two consecutive heads, more briefly bad strings. Denote the number of bad strings of length $n$ by $b_n$.

A bad string of length $n+1$ ends with either a $T$ or an $H$. If it ends in $T$, it has shape $\sigma T$, where $\sigma$ is any bad string of length $n$. If it ends with an $H$, it has shape $\sigma TH$, where $\sigma$ is any bad string of length $n-1$. That gives the Fibonacci recurrence $$b_{n+1}=b_n+b_{n-1}.$$

Calculate $b_1$ and $b_2$. Look up the closed-form "Binet" formula for Fibonacci numbers. Be careful about the indexing.

-
Now that is the type of approach I was looking for! Is it then true that, since $b_2$ = $3$ and $b_3$ = $5$ we have $b_n$ = $F_{n+3}$ since we are starting at the 5th and 6th terms of the Fibonacci sequence? (Assuming $F_n =$${0,1,1,2,3,5,8,...}$. Thus: $R(2,n) = 2^n - F_{n+3}$? – Patrick Sep 11 '13 at 18:55
It is right, except that the indexing of the Fibonacci is not done in the same way by everyone. So when you look up the Binet Formula, you do have to check, by testing at a very small $n$, or maybe two, whether the indexing is the "right" one. – André Nicolas Sep 11 '13 at 19:02
Do you happen to know of a good source of problems that are solved in this way (i.e. linear recurrence relations). I'm interested in learning more about this technique. – Patrick Sep 11 '13 at 19:34
I don't have a source, but every beginning combinatorics course has such problems. If you ask that as a question on MSE, I expect you will get useful comments/answers. – André Nicolas Sep 11 '13 at 19:38

I think I have got the answer to this problem. I believe that the formula for this would be (2n-3)/2^n.

In the case of n=2 you only get 2 heads once. When n=3 you get 2 or more heads in row 3 times: HHH, THH, HHT When n=4 you get HHHH, HHHT, THHH, HHTT, TTHH. When n=5 you get 2 or more heads in a row 5 times: HHHHH, HHHHT, THHHH, TTHHH, HHHTT, TTTHH, HHTTT.

Plug n in the formula above and you get the same answers in all the cases above.

-
I believe your answer is far, far off. – amWhy Jan 17 '15 at 16:23
you're right I just realised what I did wrong... sorry guys got the wrong answer – user208546 Jan 17 '15 at 18:43