# Flip a coin 5 times. What is the probability that heads never occurs twice in a row?

Suppose I flip a coin $5$ times in a row. There are $2^5$ possible outcomes, i.e: HHHTH, HTTTT, HTHTH, etc. I want to know the probability that heads never occurs twice in a row.

I drew out $32$ events that can occur, and I found out that the answer was $\cfrac{13}{32}$. But I'm not sure how to do this generally, because say if the coin was flipped $20$ times in a row, I wouldn't write out $2^{20}$ possibilities.

Thanks

Let $a_n$ be the number of sequences of length $n$ that do not contain two consecutive heads.

Observe that any sequence of heads and tails of length one is permissible since we cannot obtain two heads in a row. Hence, $a_1 = 2$.

Any sequence of length two is permissible except HH. Hence, $a_2 = 2^2 - 1 = 3$.

We can write a recurrence relation for a sequence of length $n$. An admissible sequence of length $n$ that ends in heads must have a tails in the $(n - 1)$st position. Hence, any sequence of length $n$ that ends in heads corresponds to an admissible sequence of length $n - 2$ to which the sequence TH is appended. There are $a_{n - 2}$ such sequences. An admissible sequence of length $n$ that ends in tails is an admissible sequence of length $n - 1$ to which a tails is appended. There are $a_{n - 1}$ such sequences. Hence, we have the recurrence relation $$a_n = a_{n - 1} + a_{n - 2}$$ Thus, the number of admissible sequences of length $n$ is given by the recursion \begin{align*} a_1 & = 2\\ a_2 & = 3\\ a_n & = a_{n - 1} + a_{n - 2}, n \geq 3 \end{align*} Notice that $a_3 = 5$, $a_4 = 8$, and $a_5 = 13$. You may recognize these as Fibonaccci numbers. In particular, $a_n = F_{n + 2}$.

The desired probability is $$\frac{a_n}{2^n}$$

• Can you clarify on what you mean by "Any sequence of heads and tails of length one is permissible since we cannot obtain two heads in a row". And how it's equal to 2? And what do you mean by "sequences of length n"? Are we referring to the sequence as the five outcomes or what do you mean by sequences? – Stuy Feb 1 '18 at 3:49
• There are two possible sequences of length $1$, H and T. Both are permissible since they do not contain two consecutive heads, so $a_1 = 2$. The possible sequences of length $2$ are HH, HT, TH, and TT. However, HH is not permissible since it contains two consecutive heads. Thus, $a_2 = 3$. If it is not already clear what I mean by sequences of length $n$, toss the coin $n$ times and record whether heads or tails appears on each throw. The result is a sequence of length $n$. – N. F. Taussig Feb 1 '18 at 11:07

You're flipping a coin f times. A possible outcome is a sequence of characters, either H or T. The number of binary sequences of length f is 2^f. The probability of a sequence with length f is 1/2^f, or 2^-f.

The number of sequences with 2 heads in a row is half the number of sequences with 2 (of anything) in a row, doubles of any kind. Which leaves the question, how many sequences (of a given length, f), don't have doubles? Only 2: HTHTHT... and THTHTH...

So the probability that heads never occurs twice, when you flip a coin $F$ times, is the number of possible outcomes ($2^F$) minus the number of sequences (of that length) that have no doubles ($2$), divided by $2$ because we only care about one of the two kinds of doubles - heads.

P(HH | f flips) = 1/2^(f-1)

TL;DR:

P(HH | coin flipped $f$ times) = P(HH or TT | $f$ flips)/2 = 1-P(neither HH nor TT | f flips) = 1 - number of outcomes without doubles/number of outcomes = 1-2/2^f = 1-1/2^(f-1) = 1/2-1/2^f. P(no HH) = 1 - P(HH) = 1/2^(f-1)

Alternate way of showing the P(no doubles): Markov Chains. After the coin has been flipped once, the coin either reads H or T. There is a 1/2 chance that after the next flip it will read the same way, which means the P(no doubles) halves.

Sequences possess a state - either they contain a double (HH or TT) or they do not. They can go from having no double to having doubles, but not vice versa.

The probability that all sequences which do not contain doubles will contain doubles after another flip is 1/2.

So after you flip it once, you have H or T. P(no doubles) = 1. You flip it again, HH, HT, TH, or TT. P(no doubles) = 1/2. Again: HHH, HHT, HTH, HTT, THH, THT, TTH, TTT. P(no doubles) = 1/4.

Since P(no doubles) halves with each flip, and is 1 when flips = 0, P(no doubles) = (1/2)^(f-1).

Let $X_n$ denote the statement "there are no two consecutive heads in $n$ coin flips", such that we want to find $P(X_n)$ (the probability of $X_n$). If we were to flip the first coin and obtain tails, then, given this information, our probability would now become $P(X_{n-1})$ (because since the tail does not affect the amount of heads, we now only care about what happens in the other $n-1$ coin flips). On the other hand, if we flip the first coin and obtain heads, we could have one of two cases

1. the second coin is also heads, and our objective has failed
2. the second coin is tails, and now our probability of success becomes $P(X_{n-2})$, because we only care about what happens in the $n-2$ flips we have not observed

These observations can be made mathematically rigorous by using the law of total probability to establish a recurrence. $$P(X_n) = P(X_n\text{ given that the first toss is Tails})P(\text{first toss is tails}) + P(X_n\text{ given that first toss is heads})P(\text{first toss is heads})$$ We know $P(X_n\text{ given that the first toss is Tails}) = P(X_{n-1})$ by the argument above, and $P(\text{first toss is tails}) = \frac{1}{2}$. We still need to work a little to find $P(X_n\text{ given that first toss is heads})$, we use the law of total probability again to divide this into the two cases I mentioned above. $$P(X_n\text{ given that first toss is heads}) = P(X_n\text{ given that first toss is heads and the second is heads})P(\text{second toss is heads}) + P(X_n\text{ given that first toss is heads and second is tails})P(\text{second toss is tails})$$ The first term is $0$ because if the first and second toss are heads, we have failed our objective. The second term is $P(X_{n-2})(\frac{1}{2})$ because we now only care about the last $n-2$ flips in the sequence. Substituting into the original equation, $$P(X_n) = \frac{1}{2}P(X_{n-1}) + \frac{1}{2}\left(\frac{1}{2}P(X_{n-2})\right) = \frac{P(X_{n-1})}{2} + \frac{P(X_{n-2})}{4}$$

You can solve for the general $n$ case using this recurrence!

For example, if you do out all the cases for $n=2,3$, you will find $P(X_2) = \frac{3}{4}$ and $P(X_3) = \frac{5}{8}$. Then, by the formula, this would mean $P(X_4) = \frac{1}{2}\frac{5}{8} + \frac{1}{4}\frac{3}{4} = \frac{8}{16} = \frac{1}{2}$ which you can check manually is true for $n=4$. Furhtermore using the formula you can calculate $P(X_5) = \frac{1}{2}\frac{1}{2} + \frac{1}{4}\frac{5}{8} = \frac{13}{32}$ which agrees with your answer!

Let head be represented by 0 and tail by 1. Then a sequence of heads and tails can be represented by a binary number.

For 2 tosses ($n = 2$), the possible sequences are:

00
01
10
11


There are $2^2$ total possible sequences and among them the number of sequences where heads never occurs twice in a row is 3. So for $n = 2$, the probability of heads never occurs twice in a row is $P_2=\frac{3}{4}$.

Similarly, for $n = 3$, the sequences are:

000
001
010
011
100
101
110
111


Again there are $2^3$ total possible sequences, and 5 of them with heads never occurs twice in a row. So $P_3=\frac{5}{8}$.

To find the general formula for calculating $P_n$, lets make the following observation:

1. When adding a new most significant digit to get the binary numbers of $n$ digits, for example, to expend the numbers from $n=2$ to $n=3$ above, we make 2 copies of all of the binary numbers of $n-1$ digits, add $0$s to left of the top copy and $1$s to the bottom copy.
2. The top quarter of the new binary numbers all has two $0$s at the beginning.
3. The second quarter of the new binary numbers has the same number of sequences, where heads never occurs twice, as that of $n-2$, that is $2^{n-2}P_{n-2}$.
4. The bottom half of the new binary numbers has the same number of sequences, where heads never occurs twice, as that of $n-1$, that is $2^{n-1}P_{n-1}$.

Based on these observations we have:

$$P_n = \frac{2^{n-2}P_{n-2} + 2^{n-1}P_{n-1}}{2^n} = \frac{\frac{1}{2}P_{n-2} + P_{n-1}}{2}$$

Using this recursive formula, we get: $$P_4=\frac{\frac{1}{2}P_2+P_3}{2}=\frac{\frac{1}{2}\frac{3}{4}+\frac{5}{8}}{2}=\frac{1}{2}$$ $$P_5=\frac{\frac{1}{2}P_3+P_4}{2}=\frac{\frac{1}{2}\frac{5}{8}+\frac{1}{2}}{2}=\frac{13}{32}$$ $$P_6=\frac{\frac{1}{2}P_4+P_5}{2}=\frac{\frac{1}{2}\frac{3}{4}+\frac{5}{8}}{2}=\frac{21}{64}$$