Conditional probability of no run of $4$ consecutive heads in $n$ coin flips

Question

Let the probability that there is no run of 4 consecutive heads when a fair coin is flipped $n$ times be $u_{n}$. Show that

$$u_{n} = \frac{1}{2}u_{n-1} + \frac{1}{4}u_{n-2} + \frac{1}{8}u_{n-3} + \frac{1}{16}u_{n-4}.$$

This is obviously meant to be derived by conditioning / partition theorem, but I don't see how, since $u_{n}$ depends on whether $(n-4)$th throw ended with heads or tails (assuming no run of $4$ heads in $(n-4)$ throws). For example, if $(n-4)$-th flip ended with tails, then $u_{n} = \frac{15}{16}$, but if $(n-4)$ ended with heads, then $u_{n}$ is something else (I don't know what). So we have to somehow condition on $(n-4)$th throw either ending in heads or tails. But I have no clue what to do with this, after thinking about this for hours.

How to solve this?

Answer 1

In my opinion, problems of the form "calculate the number of sequences with some property of a given length" lend themselves well to recursive approaches.

Let $P(n)$ be the set of all $n$ flip sequences with no $4$ heads in a row.

Let $a_1,\ldots,a_n,a_{n+1}\in P(n+1)$. If $a_{n+1}=T$, $a_1,\ldots,a_n$ can be any element of $P(n)$. If $a_{n+1}=H$ and $a_n=T$, $a_1,\ldots,a_{n-1}$ can be any element of $P(n-1)$. Similarly, if $a_{n+1}=a_n=H$, and $a_{n-1}=T$, $a_1,\ldots,a_{n-2}$ can be any element of $P(n-2)$. And again, if $a_{n+1}=a_n=a_{n-1}=H$, and $a_{n-2}=T$, $a_1,\ldots,a_{n-3}$ can be any element of $P(n-3)$. Obviously, $a_{n+1}=a_n=a_{n-1}=a_{n-2}=H$ is not allowed. So these are all of the possibilities.

Do you see why this implies the given relation?

Answer 2

Let's think of some ways a sequence of $n$ flips could avoid an $HHHH$ sequence:

• Our sequence could end with a tail, $...T$, and the first $(n-1)$ flips could avoid $HHHH$. These two events happen independently, and the probability that both of them happen is $\frac{1}{2} u_{n-1}$.

• Of course, there are sequences of $n$ flips that end with a head, $...H$, but avoid $HHHH$. One class of such sequences ends in $...TH$ and avoids $HHHH$ in the first $(n-2)$ flips. Once again, these events happen independently, and their probability is $\frac{1}{2} * \frac{1}{2} * u_{n-2} = \frac{1}{4} u_{n-2}$.

• What about sequences of $n$ flips that end in a double head, $...HH$, and avoid $HHHH$? Once again, one class of such sequences ends $...THH$ and avoids $HHHH$ in the first $(n-3)$ flips. You see where this is going: this is the $\frac{1}{8} u_{n-3}$ term.

• The final and rarest possibility is that our sequence ends in a triple head, $...HHH$, and avoids $HHHH$. In order to do this, we must have a $T$ before our triple $H$, so our sequence ends $...THHH$ and the first $(n-4)$ flips avoid $HHHH$ with probability $\frac{1}{16}u_{n-4}$.

These four possibilities are mutually exclusive, and an $HHHH$-avoiding sequence must end in one of them, so they partition the event $E_n = \{ \text{ no } HHHH \text{ in } n \text{ flips,} \}$ which instantly gives us the desired recurrence relation.