6

Suppose we flip a fair coin $n$ times, what is the probability that no three consecutive heads occur?

I understand the proof for the case with no two consecutive heads, where we can consider the number of sequences that start with $H$ and $T$ and get the recurrence relations $$F(n+1) = F(n) + F(n-1) $$ where $F(n)$ is the number of sequences with no consecutive heads which leads to $$Q_n = \frac{1}{2}Q_{n-1} + \frac{1}{4}Q_{n-2}$$ However, I'm having trouble extending to the case of no three consecutive heads. What would the recurrence relations be for the number of sequences?

  • 1
    Here you will have to extend the same line of thinking to a larger set now. Think about what happens if the first two letters contain a $T$ now, and what happens if they contain $HH$. – Sarvesh Ravichandran Iyer Dec 14 '17 at 05:01
  • @астонвіллаолофмэллбэрг If a sequence has first two letters that contain a $T$, we still have to split into the cases where the $T$ is in front or in the back. I can construct four counts for the four types of sequences that start with $HH$, $HT$, $TH$, and $TT$ but I don't know how to combine them into a recurrence relations. –  Dec 14 '17 at 05:11

2 Answers2

9

Let $H(n)$ be the number of coin flips without $3$ consecutive heads.

$$H(n) = H(n-1) + H(n-2) + H(n-3)$$ for $n \ge 3$

To prove this consider a string of $H$ and $T$ that is $n$ long. Valid constructions of this may either end in a $T$, which may happen by taking any valid string on $n-1$ and appending a $T$ (there are $H(n-1)$ ways to do this), or may end in $TH$, which can be done by taking any valid string on $n-2$ and appending $TH$ to it (this can happen in $H(n-2)$ ways) and finally it may end with $THH$, which can be formed by taking any valid string on $n-3$ and appending $THH$ (which may happen in $H(n-3)$ ways.

This gives us our equation above as this covers all possibilities.

Benji Altman
  • 1,237
3

Let $A_n$ be the number of strings of length $n$ without three consecutive heads that end with $T,$ $B_n$ be the number that end with $TH$ and $C_n$ the number that end with $HH$.

Then $$ A_{n+1} = A_n + B_n + C_n,$$ $$ B_{n+1} = A_n,$$ and $$ C_{n+1} = B_n.$$

spaceisdarkgreen
  • 58,508