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

Question

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

Answer 1

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}$$

Answer 2

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} $$

Answer 3

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).