# N coin flips with at least three times heads or tails in a row (recursive probability)

Suppose I'll be flipping a fair coin $n$ times. Now I want to calculate the probability that I'll get at least three times heads or tails in a row.

The goal of this exercise is to get a recurrence formula of this kind.

$p_n = a \cdot p_{n-1} + b \cdot p_{n-2} + c \qquad (n\geq 3)$

And we have to use the law of total probability to get to the recursion.

I got to a formula with a different way. Suppose $q_n$ is the number of constellations that do not have three heads or tails. Then with $q_1=2$ and $q_2=4$ (because then 3xH or 3xT is not possible) we have $q_n = q_{n-1}+q_{n-2}$. Then

$p_n = \frac{2^n - q_n}{2^n}$

This is obviously not the way I have to tackle this problem. How do I get a recursion with the law of total probability?

-

Let $p_n$ be the probability of getting a sequence of three heads or tails in $n$ trials.

• For $n$ trials, whatever the first flip is, the second will either be a repeat of it or it will not. $\frac 12$ chance of either:

• If it's not a repeat, we recurse for $n-1$ trials. This is: $p_{n-1}$

• If it is a repeat, then the third coin will either be a repeat or it will not, at $\frac 12$ chance of either:

• If it is not a repeat, we recurse for $n-2$ trials. That is: $p_{n-2}$

• If it is a repeat we have encountered a sequence of three heads or tails.

$\therefore p_n = \underline{\text{ ? }}\; p_{n-1} + \underline{\text{ ? }}\; p_{n-2} + \underline{\text{ ? }}$

Base case: $p_1=0, p_2=0, p_3 = \frac 14$ and so on.

Fill in the blanks.

Let $T_n$ be the event that a string of $n$ coin flips contains a substring of either three heads or of three tails.

Let $D_x$ be the event that the $x$ indexed flip in a sequence repeats the result of the $x-1$ indexed flip. Each event is conditionally independent because whatever the previous flip result, the probability of repeating it remains identical (for unbiased coins).

By the Law of Total Probability: \begin{align} \operatorname{P}(T_n) &= \operatorname{P}(T_n \cap D_2) + \operatorname{P}(T_n\cap \neg D_2) \\ & = \operatorname{P}(T_n\mid D_2)\operatorname{P}(D_2) + \operatorname{P}(T_n\mid \neg D_2)\operatorname{P}(\neg D_2) \\ & = \operatorname{P}(T_n\mid D_2, D_3)\operatorname{P}(D_3)P(D_2) + \operatorname{P}(T_n\mid D_2, \neg D_3)\operatorname{P}(\neg D_3)\operatorname{P}(D_2) + \operatorname{P}(T_n\mid \neg D_2)\operatorname{P}(\neg D_2) \end{align}

Now $\operatorname{P}(T_n\mid \neg D_2) = \operatorname{P}(T_{n-1})$ since, when given the second flip is not a duplicate then the first flip cannot be part of the sought substring, so it is only possible to find it among the remaining string of $n-1$ flips.

Similarly $\operatorname{P}(T_n \mid D_2,\neg D_3) = \operatorname{P}(T_{n-2})$.

However, since if the second and third flips are both duplicates of the first flip, then we have found the sought substring, so: $\operatorname{P}(T_n\mid D_2, D_3) = 1$

So: \begin{align} \operatorname{P}(T_n) & = 1\times \operatorname{P}(D_3)\operatorname{P}(D_2) + \operatorname{P}(T_{n-2})\operatorname{P}(\neg D_3)\operatorname{P}(D_2) + \operatorname{P}(T_{n-1})\operatorname{P}(\neg D_2) \end{align}

-
Yes. So I get $p_n = \frac{1}{2}p_{n-1} + \frac{1}{4}p_{n-2} + \frac{1}{4}$. But where does the law of total probability come to play? I know that a solution is good but this is the wrong way to get there. – sebastian May 27 '14 at 8:17
@sebastian It is a total probability argument. At each node, you can only either go down one branch, or you can go down the other. The branch points are mutually exclusive and exhaustive. As the edit demonstrates. – Graham Kemp May 27 '14 at 12:03
Law of Total Probability is: $P(A) = P(A \mathop{\cap}_{\forall x} B_x)$, where the set $\{B_x\}$ contains mutually exclusive and exhaustive events. – Graham Kemp May 27 '14 at 12:06
Thank you for this detailed explanation. – sebastian May 28 '14 at 8:49