# Probability of tossing a fair coin with at least $k$ consecutive heads

Tossing a fair coin for $N$ times and we get a result series as $HTHTHHTT\dots~$, Here '$H$' denotes 'head' and '$T$' denotes 'tail' for a specific tossing each time.

What is the probability that the length of the longest streak of consecutive heads is greater than or equal to $k$? (that is we have a $HHHH\dots~$, which is the substring of our tossing result, and whose length is greater than or equal to $k$)

I came up with a recursive solution (though not quite sure), but cannot find a closed form solution.

Here is my solution.

Denote $P(N,k)$ as the probability for tossing the coin $N$ times, and the longest continuous heads is greater or equal than $k$. Then (For $N>k$)

$$P(N,k)=P(N-1,k)+\Big(1-P(N-k-1,k)\Big)\left(\frac{1}{2}\right)^{k+1}$$

-
Your example sequence reminded me of this brilliant Simpsons scene :-) –  joriki Nov 10 '12 at 8:58
I'm getting $(N-k+1)/2^k$ for the closed form. Would you like for me to post my solution, or do you want to think about it some more before I spoil the beans? –  Braindead Nov 10 '12 at 8:59
@Braindead: That can't be right; it's $\gt1$ for small $k$. –  joriki Nov 10 '12 at 9:00
Duh, you are right. I overcounted. –  Braindead Nov 10 '12 at 9:08
I tried to clarify some of the formulations; please check whether I preserved the intended meaning. In particular, I assumed that you had merely accidentally written "greater" once instead of "greater or equal". –  joriki Nov 10 '12 at 9:12

Your recurrence relation is correct. I don't think you can do much better than that for general $k$, but you can find a closed form for specific values of $k$. For the first non-trivial value of $k$, the recurrence relation is

$$p_n=p_{n-1}+(1-p_{n-3})/8\;.$$

With $p_n=1+\lambda^n$, the characteristic equation becomes $\lambda^3-\lambda^2+1/8=0$. One solution, $\lambda=1/2$, can be guessed, and then factoring yields $(\lambda-1/2)(\lambda^2-\lambda/2-1/4)$ with the further solutions $\lambda=(1\pm\sqrt5)/4$. Thus the general solution is

$$p_n=1+c_1\left(\frac12\right)^n+c_2\left(\frac{1+\sqrt5}4\right)^n+c_3\left(\frac{1-\sqrt5}4\right)^n\;.$$

The initial conditions $p_0=0$, $p_1=0$, $p_2=1/4$ determine $c_1=0$, $c_2=-(1+3/\sqrt5)/2$ and $c_3=-(1-3/\sqrt5)/2$, so the probability is

\begin{align} p_n &=1-\frac{1+3/\sqrt5}2\left(\frac{1+\sqrt5}4\right)^n-\frac{1-3/\sqrt5}2\left(\frac{1-\sqrt5}4\right)^n\\ &=1-\frac4{\sqrt5}\left(\left(\frac{1+\sqrt5}4\right)^{n+2}-\left(\frac{1-\sqrt5}4\right)^{n+2}\right)\;. \end{align}

Thus, for large $n$ the probability approaches $1$ geometrically with ratio $(1+\sqrt5)/4\approx0.809$.

-