Take the 2-minute tour ×
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.

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

What is the expected number of coin tosses?

share|improve this question
2  
Yet another copy and paste from Brilliant.org: brilliant.org/i/5rCgJ3 –  Erick Wong Apr 17 '13 at 5:49
2  
@ErickWong: Is this a recent problem on brilliant.org? –  robjohn Apr 17 '13 at 8:48
add comment

4 Answers 4

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|improve this answer
add comment

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|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
1  
@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
add comment

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|improve this answer
add comment

Lets calculate it for n consecutive tosses the expected number of tosses needed Lets say that for En-1 for n-1 consecutive heads and En for n consecutive heads Now if we get one more head after En-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.En-1 +1 2.En +1 1 for a tail

So En=1/2*(En-1 +1)+1/2(En-1+ En+ 1) So En= 2En-1+2 So we have the general recurrence relation as f(x)=2*f(x-1)+2 where for x>=2 and for n=2 we can easily derive that f(2)=6; So f(x)=2*f(x-1)+2=f(x)=2*(2*f(x-2)+2)+2=2*(2*(2*f(x-3)+2)+2)+2 which can be generalized as f(x)=2^x+2^1 +2^2+2^3+....... 2^(n-1) =2^x+2*(2^(n-1)-1) So for x=5 it will be 32+2*(2^4-1)=62

share|improve this answer
add comment

Your Answer

 
discard

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.