Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

What is the expected number of coin tosses?

share|cite|improve this question
Yet another copy and paste from – Erick Wong Apr 17 '13 at 5:49
@ErickWong: Is this a recent problem on – robjohn Apr 17 '13 at 8:48

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

share|cite|improve this answer
It is clear that e is finite, but how can you show it properly though ? Thanks. – Dark Jul 3 '15 at 17:39
If one wants, let $X$ be the number of tosses. Then $\Pr(X=n)\le (1/2)^{n-5}$. So $E(X)\le \sum n (1/2)^{n-5}$, a convergent series. – André Nicolas Jul 3 '15 at 17:58
The same method obviously generalizes to give $e_n$, the expected number of tosses to get $n$ consecutive heads ($n \ge 1$): $$e_n=\frac{1}{2}(e_n+1)+\frac{1}{4}(e_n+2)+\frac{1}{8}(e_n+3)+\frac{1}{16}(e_n+‌​4)+\cdots +\frac{1}{2^n}(e_n+n)+\frac{1}{2^n}(n),$$ the solution of which is easily found to be $$e_n = 2(2^n - 1).$$ – r.e.s. Jul 19 '15 at 23:57
Yes, good point. The most common assigned problem is expected number of tosses until two heads in a row, answer $6$. We can use the same idea for $n$ heads in a row, probability of head $p$. – André Nicolas Jul 20 '15 at 0:12

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

share|cite|improve this answer
Could you elaborate briefly on why the derivative gives the expected number of flips? – Austin Mohr Aug 20 '13 at 2:37
@AustinMohr: If $f(x)$ is the generating function of the probability $p_n$ of the ending after $n$ tosses $$ f(x)=\sum_{n=0}^\infty p_nx^n $$ then, because the probability of lasting an infinite number of tosses is $0$, we have $$ \begin{align} f(1) &=\sum_{n=0}^\infty p_n\\ &=1 \end{align} $$ Furthermore, $$ \begin{align} f'(1) &=\sum_{n=0}^\infty n\,p_n\\ &=\mathrm{E}(n) \end{align} $$ – robjohn Aug 20 '13 at 5:13
Do you know how to find the distribution (or expectation and variance) for the number of tosses until either 5 consecutive heads or 5 consecutive tails? (Or 5 consecutive equal results from rolling dice.) Is there a question on about this? – ShreevatsaR Dec 15 '15 at 14:17
I found an answer using martingales here:… but I'm curious if there is a generating functions way (also about the distribution, say variance or number of trials until 90% probability of seeing what we want). – ShreevatsaR Dec 15 '15 at 14:31
@ShreevatsaR: The generating function for the probability of ending on $n$ tosses for that problem is similar: $$\frac{\frac1{16}x^5}{1-\left(\frac12x+\frac14x^2 +\frac18x^3+\frac1{16}x^4\right)}$$ From that, we can compute the expectation and variance. Looking at the coefficients of the series for the generating function we can also find out that in $66 $ tosses, we will have a $90.0761\%$ chance of seeing $5$ heads or $5$ tails in a row. – robjohn Dec 15 '15 at 17:32

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.

share|cite|improve this answer
What tool did you use for solving? – pushpen.paul May 11 '15 at 17:19
@pushpen.paul I used Mathematica – Sasha May 11 '15 at 17:20

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

share|cite|improve this answer

The question can be generalized to what is the expected number of tosses before we get x heads.Let's call this E(x). We can easily derive a recursive formula for E(x). Now, there are a total of two possibilities, first is that we fail to get the xth consecutive heads in xth attempt and second, we succeed. Probability of success is 1/(2^x) and probability of failure is 1-(1/(2^x)).

Now, if we were to fail to get xth consecutive heads in xth toss (i.e. case 1), the we will have to use a total of (E(x)+1) moves, because one move has been wasted.

On the other hand if we were to succeed in getting xth consecutive head in xth toss (i.e. case 2), the total moves is E(x-1)+1 , because we now take one move more than that was required to get x-1 consecutive heads.


E(x) = P(failure) * (E(x)+1) + P(success) * (E(x-1)+1)
E(x) = [1-(1/(2^x))] * (E(x)+1) + [1/(2^x)] * (E(x-1)+1)

Also E(0) = 0 , because expected number of tosses to get 0 heads is zero, duh


E(1) = (1-0.5) * (E(1)+1) + (0.5) * (E(0)+1) => E(1) = 2

E(2) = (1-0.125) * (E(1)+1) + (0.125) * (E(1)+1) => E(2) = 6


E(3) = 14

E(4) = 30

E(5) = 62

share|cite|improve this answer

Expectation for getting n consecutive heads is : 2*(2^n-1). Thus for 5 heads it is = 62.

share|cite|improve this answer
How did you get the formula? – pushpen.paul May 11 '15 at 18:25

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.