Expected Number of Coin Tosses to Get Five Consecutive Heads

Question

A fair coin is tossed repeatedly until 5 consecutive heads occurs.

What is the expected number of coin tosses?

Answer 1

This problem is solvable with the next step conditioning method. Let $\mu_k$ denote the mean number of tosses until 5 consecutive heads occurs, given that $k$ consecutive heads just occured. Obviously $\mu_5=0$. Conditioning on the outcome of the next coin throw: $$ \mu_k = 1 + \frac{1}{2} \mu_{k+1} + \frac{1}{2} \mu_0 $$ Solving the resulting linear system:

In[28]:= Solve[Table[mu[k] == 1 + 1/2 mu[k + 1] + mu[0]/2, {k, 0, 4}],
   Table[mu[k], {k, 0, 4}]] /. mu[5] -> 0

Out[28]= {{mu[0] -> 62, mu[1] -> 60, mu[2] -> 56, mu[3] -> 48, 
  mu[4] -> 32}}

Hence the expected number of coin flips $\mu_0$ equals 62.

Answer 2

Let $e$ be the expected number of tosses. It is clear that $e$ is finite.

Start tossing. If we get a tail immediately (probability $\frac{1}{2}$) then the expected number is $e+1$. If we get a head then a tail (probability $\frac{1}{4}$), then the expected number is $e+2$. Continue $\dots$. If we get $4$ heads then a tail, the expected number is $e+5$. Finally, if our first $5$ tosses are heads, then the expected number is $5$. Thus $$e=\frac{1}{2}(e+1)+\frac{1}{4}(e+2)+\frac{1}{8}(e+3)+\frac{1}{16}(e+4)+\frac{1}{32}(e+5)+\frac{1}{32}(5).$$ Solve this linear equation for $e$. We get $e=62$.

Answer 3

Here is a generating function approach.

Consider the following toss strings, probabilities, and terms

$$ \color{#00A000}{ \begin{array}{llc} T&\frac12&\qquad\frac12x\\ HT&\frac14&\qquad\frac14x^2\\ HHT&\frac18&\qquad\frac18x^3\\ HHHT&\frac1{16}&\qquad\frac1{16}x^4\\ HHHHT&\frac1{32}&\qquad\frac1{32}x^5\\ \color{#C00000}{HHHHH}&\color{#C00000}{\frac1{32}}&\color{#C00000}{\qquad\frac1{32}x^5} \end{array} } $$ Each term has the probability as its coefficient and the length of the string as its exponent.

Possible outcomes are any combination of the green strings followed by the red string. We get the generating function of the probability of ending after $n$ tosses to be $$ \begin{align} f(x)&=\sum_{k=0}^\infty\left(\frac12x+\frac14x^2+\frac18x^3+\frac1{16}x^4+\frac1{32}x^5\right)^k\frac1{32}x^5\\ &=\frac{\frac1{32}x^5}{1-\left(\frac12x+\frac14x^2+\frac18x^3+\frac1{16}x^4+\frac1{32}x^5\right)}\\ &=\frac{\frac1{32}x^5}{1-\frac{\frac12x-\frac1{64}x^6}{1-\frac12x}}\\ &=\frac{\frac1{32}x^5-\frac1{64}x^6}{1-x+\frac1{64}x^6} \end{align} $$ The average duration is then $$ \begin{align} f'(1) &=\left.\frac{\left(\frac5{32}x^4-\frac6{64}x^5\right)\left(1-x+\frac1{64}x^6\right)-\left(\frac1{32}x^5-\frac1{64}x^6\right)\left(-1+\frac6{64}x^5\right)}{\left(1-x+\frac1{64}x^6\right)^2}\right|_{\large x=1}\\ &=\frac{\frac4{64}\frac1{64}+\frac1{64}\frac{58}{64}}{\left(\frac1{64}\right)^2}\\[12pt] &=62 \end{align} $$

Answer 4

Lets calculate it for $n$ consecutive tosses the expected number of tosses needed.

Lets denote $E_n$ for $n$ consecutive heads. Now if we get one more head after $E_{n-1}$, then we have $n$ consecutive heads or if it is a tail then again we have to repeat the procedure.

So for the two scenarios:

1. $E_{n-1}+1$
2. $E_{n}{+1}$ ($1$ for a tail)

So, $E_n=\frac12(E_{n-1} +1)+\frac12(E_{n-1}+ E_n+ 1)$, so $E_n= 2E_{n-1}+2$.

We have the general recurrence relation. Define $f(n)=E_n+2$ with $f(0)=2$. So,

\begin{align} f(n)&=2f(n-1) \\ \implies f(n)&=2^{n+1} \end{align}

Therefore, $E_n = 2^{n+1}-2 = 2(2^n-1)$

For $n=5$, it will give us $2(2^5-1)=62$.

Answer 5

We can solve this without equations. Ask the following (auxiliary) question: how many flips you need to get either $N$ heads or $N$ tails. Then to get $N$ heads only you need twice as many flips. Start with the question of how many flips you need to get either $H$ or $T$. The answer is $$x = \frac12 (1) + \frac12 (1) = 1.$$ The reason is that there is $\frac12$ probability to get $H$, and after $1$ flip you are done. The same for $T$. To get only one $H$ you then need two flips. OK. Now we ask what it takes to get $HH$ or $TT$. The result is $$x=\frac12(1+2) + \frac12(1+2).$$ The number $2$ appears because, say you flip $H$ first, then you need on average $2$ flips to get another $H$, as we learned earlier. The same for $T$. So you need $3$ flips to get $TT$ or $HH$, and you need $6$ flips to get $HH$ only. And so on. You need $\frac12 (1+6) + \frac12(1+6) = 7$ flips to get either $HHH$ or $TTT$, and $14$ to get $HHH$ only. If you need $HHHH$ or $TTTT$, then flip $\frac12(1+14) + \frac12(1+14) = 15$ times, or $30$ times to get just $HHHH$. The sequence is $1, 3, 7, 15, \ldots$ to get either heads or tails. The formula is easy to extract: you need $2^N-1$ flips to get either $N$ heads or $N$ tails, or $2^{N+1}-2$ to get $N$ heads only. If $N=5$ we get the answer: $62$.

Answer 6

Here is an answer that uses martingale. We think in terms of a game: at every time step we toss a coin, you can bet any amount $x$; if the coin toss comes up head, you gain $x$, otherwise you lose $x$. Now let's construct a strategy such as if the $n$th coin toss is tail, then you position (cumulative gain) will be $-n$. So clearly, we should bet 1 on the first toss. If we get a tail, our position is -1, and we will bet 1 again; if we get a head, our position is 1, and we should bet 3 next, since we want to get to -2 if the second toss is a tail. How much should we bet after 2 heads in a row? Let's say the next toss is the $k+1$th toss, then $k-2$th toss was a tail, and by our strategy, our position after $k-2$th toss was $-(k-2)$; after that we bet 1, a head showed up, and then we bet 3, again a head, so our position now is $-(k-2)+4=-k+6$. We want to get to $-(k+1)=-k-1$, so we should bet 7 on the $k+1$th toss. By the same reasoning, we should bet 15 after the third head in a row, and 31 after the fourth head in a row. Since the up and down are symmetric, our position $X$ is a martingale. Let $\tau$ be the first time we have 5 consecutive heads. $\tau$ has finite expectation, so by optional sampling theorem, $X$ stopped at $\tau$ is also a martingale. What is our position at $\tau$? According to our strategy, our position will be $-(\tau-5)+1+3+7+15+31=-\tau+62$. Since our position stopped at $\tau$ is a martingale, and our position starts at 0, this means $$\mathbb{E}[-\tau+62]=0$$ and $$\mathbb{E}[\tau]=62$$

Answer 7

Peter Winkler included this problem in his puzzle collection Mathematical Puzzles (2020), and gave the following very elegant solution, which I quote below:

Since the probability of seeing HHHHH in a particular series of five coin flips is $1/32$, you might think it would take $32$ flips on average to get HHHHH. Indeed, $32$ flips is the average wait between occurrences of HHHHH, but this includes, for example, a wait of length 1 between the first five heads in HHHHHH [six H's] and the last five. Waits of length 1 can’t help us, because we have no “head start” (OK, pun intended) when we begin flipping.

The real answer is much greater. Between runs, half the time you get the wait of $1$ and the rest of the time $1+x$, where $x$ is the desired quantity. Hence it is not $x$ but the average of $1$ and $1+x$ that is equal to $32$, which gives us $x = 62$.