Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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} $$

share|improve this question
    
Your example sequence reminded me of this brilliant Simpsons scene :-) –  joriki Nov 10 '12 at 8:58
1  
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
show 4 more comments

1 Answer 1

up vote 2 down vote accepted

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$.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.