What's the probabality of at most two consecutive heads in N coin flips?

Question

I tried solving using recursion but am not sure whether my answer is correct.

I tried using P(N) = P(N-1)*0.25*1 (For the last two TT) + P(N-1)*0.25*1 (For the last two HT) + P(N-1)*0.25*1 (For the last two TH) + P(N-1)*0.25*0.5 (For the last two HH, since it can be followed only by T)

Post your ideas, it is more useful to discuss them rather than showing a solution out of the blue — Angelo Rendina, Sep 10 '16 at 16:37
Post your answer, and how you arrived at it. Then we can either verify it or show where you may have gone wrong, and why. — amWhy, Sep 10 '16 at 16:42

score 1 · Accepted Answer · answered Sep 10 '16 at 18:01

Let's count the toss sequences with no triple $HHH$. Let $T_n$ be the number of such, of length $n$. Of course, the answer you seek is $\frac {T_n}{2^n}$.

Let $A_n$ be those "good" sequences of length $n$ that end in $T$, let $B_n$ be those that end in $TH$, and let $C_n$ be those that end in $THH$. Then $$T_n=A_n+B_n+C_n$$ Furthermore, $$A_n=T_{n-1}\quad B_n=A_{n-1}=T_{n-2}\quad C_n=B_{n-1}=T_{n-2}$$ Whence $$T_n=T_{n-1}+T_{n-2}+T_{n-3}$$ Clearly we have $T_1=2,\;T_2=4,\;T_3=7$

I'm not aware of a pleasant closed formula, though of course standard methods will give an expression in terms of the roots of the associated cubic. See this for some details. Of course it's easy to implement the recursion for modest $N$.

What's the probabality of at most two consecutive heads in N coin flips?

1 Answers1