60
$\begingroup$

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

What is the expected number of coin tosses?

|cite|improve this question
$\endgroup$
  • 4
    $\begingroup$ Yet another copy and paste from Brilliant.org: brilliant.org/i/5rCgJ3 $\endgroup$ – Erick Wong Apr 17 '13 at 5:49
  • 2
    $\begingroup$ @ErickWong: Is this a recent problem on brilliant.org? $\endgroup$ – robjohn♦ Apr 17 '13 at 8:48

10 Answers 10

80
$\begingroup$

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

|cite|improve this answer
$\endgroup$
  • 1
    $\begingroup$ It is clear that e is finite, but how can you show it properly though ? Thanks. $\endgroup$ – Dark Jul 3 '15 at 17:39
  • 2
    $\begingroup$ 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. $\endgroup$ – André Nicolas Jul 3 '15 at 17:58
  • 15
    $\begingroup$ 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).$$ $\endgroup$ – r.e.s. Jul 19 '15 at 23:57
  • 4
    $\begingroup$ Why are TT, TTT not considered? $\endgroup$ – Jaydev Jul 24 '17 at 1:24
  • 4
    $\begingroup$ @Jaydev TT and TTT both are covered by the case "if we get a tail immediately". $\endgroup$ – David K Oct 6 '17 at 13:13
21
$\begingroup$

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

|cite|improve this answer
$\endgroup$
  • 1
    $\begingroup$ Could you elaborate briefly on why the derivative gives the expected number of flips? $\endgroup$ – Austin Mohr Aug 20 '13 at 2:37
  • 2
    $\begingroup$ @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} $$ $\endgroup$ – robjohn♦ Aug 20 '13 at 5:13
  • $\begingroup$ 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 math.se about this? $\endgroup$ – ShreevatsaR Dec 15 '15 at 14:17
  • $\begingroup$ I found an answer using martingales here: quora.com/… 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). $\endgroup$ – ShreevatsaR Dec 15 '15 at 14:31
  • $\begingroup$ @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. $\endgroup$ – robjohn♦ Dec 15 '15 at 17:32
18
$\begingroup$

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

|cite|improve this answer
$\endgroup$
  • 1
    $\begingroup$ Amazing solution, thank you $\endgroup$ – Jaydev Jul 24 '17 at 1:30
11
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ What tool did you use for solving? $\endgroup$ – pushpen.paul May 11 '15 at 17:19
  • $\begingroup$ @pushpen.paul I used Mathematica $\endgroup$ – Sasha May 11 '15 at 17:20
  • $\begingroup$ Can you please explain the original equation? $\endgroup$ – BOS Sep 20 '16 at 15:58
  • $\begingroup$ @BOS Since $\mu_k$ is the conditional expectation, consider the next coin toss. Because a new toss was made, we add 1, in the next state, with equal probabilities we either get next head, in which case we gonna get $k+1$ heads, hence $\mu_{k+1}$, or the tail, in which case we break the streak of consecutive heads, hence $\mu_0$. $\endgroup$ – Sasha Sep 23 '16 at 3:03
  • 1
    $\begingroup$ @Sasha This is the Markov way of solving it, right? This seems most intuitive to me of all methods presented here. $\endgroup$ – user3496060 Dec 22 '17 at 8:06
2
$\begingroup$

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.

So,

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

now,

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

Similarly,

E(3) = 14

E(4) = 30

E(5) = 62

|cite|improve this answer
$\endgroup$
1
$\begingroup$

I would simplify the problem as follows:

Let $e$ = Expected number of flips until $5$ consecutive $H$, i.e., $E[5H]$
Let $f$ = Expected number of flips until $5$ consecutive $H$ when we have seen one $H$, i.e., $E[5H|H]$
Let $g$ = Expected number of flips until $5$ consecutive $H$ when we have seen two $H$, i.e., $E[5H|2H]$
Let $h$ = Expected number of flips until $5$ consecutive $H$ when we have seen three $H$, i.e., $E[5H|3H]$
Let $i$ = Expected number of flips until $5$ consecutive $H$ when we have seen four $H$, i.e., $E[5H|4H]$

Now Start flipping coin, there is $\frac{1}{2}$ probability of getting $H$ or $T$. So if we get $H$ then expected number of flips until 5 consecutive $H$ is $(f+1)$. Alternatively if $T$, we wasted 1 flip and expected number is still $(e+1)$ $$ e=\frac12(e+1)+\frac12(f+1)\; $$

We now need $f$ to solve above to get $e$. Now we start with 1 $H$ and seeking 4 more $H$ to get total 5 $H$. Again, there is $\frac{1}{2}$ probability of getting $H$ or $T$. So if we get $H$ (total $2H$ so far) then expected number of flips until 5 consecutive $H$ is $(g+1)$. Alternatively if $T$, we wasted this flip and expected number is back to $(e+1)$

$$ f=\frac12(g+1)+\frac12(e+1)\; $$

Continuing this way... $$ g=\frac12(h+1)+\frac12(e+1)\; $$ $$ h=\frac12(i+1)+\frac12(e+1)\; $$

Finally, Now we have 4 $H$ and seeking last $H$ to get total 5 $H$. Still, there is $\frac{1}{2}$ probability of getting $H$ or $T$. So if we get $H$ (total $5H$) then we need just $1$ flip. Alternatively if $T$ is observed, we wasted this flip and expected number is back to $(e+1)$ $$ i=\frac12(1)+\frac12(e+1)\; $$

Solving these equations, $e=62$, $f=60$, $g=56$, $h=48$, $i=32$
This solution offers some insight into conditional expectations of number of flips needed till 5 consecutive $H$ given 1, 2, 3 and 4 consecutive $H$.

|cite|improve this answer
$\endgroup$
0
$\begingroup$

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

|cite|improve this answer
$\endgroup$
  • 6
    $\begingroup$ How did you get the formula? $\endgroup$ – pushpen.paul May 11 '15 at 18:25
0
$\begingroup$

No one else seems to have suggested the following approach. Suppose we keep flipping a coin until we get five heads in a row. Define a "run" as either five consecutive heads or a tails flip plus the preceding streak of heads flips. (A run could be a single tails flip.) The number of coin flips is equal to the number of runs with at least four heads ($R_{4+}$), plus the number of runs with at least three heads ($R_{3+}$), and so on down to the number of runs with at least zero heads ($R_{0+}$). We can see this by expanding the terms:

$R_{0+}$ = # runs with 0 heads + # runs with 1 head + ... + # runs with 5 heads

$R_{1+}$ = # runs with 1 head + # runs with 2 heads + ... + # runs with 5 heads

...

$R_{4+}$ = # runs with 4 heads + # runs with 5 heads

# flips = # flips in runs with 0 heads + # flips in runs with 1 head + ... + # flips in runs with 5 heads

# flips in runs with 0 heads = # runs with 0 heads

# flips in runs with 1 head = 2 x # runs with 1 head

...

# flips in runs with 4 heads = 5 x # runs with 4 heads

# flips in runs with 5 heads = 5 x # runs with 5 heads

By linearity of expectation, the expected number of coin flips is $E(R_{0+}) + E(R_{1+}) + \ldots + E(R_{4+})$. $E(R_{4+})$ is $2 E(R_{5+}) = 2$, because one half of the time we flip at least four heads in a row, we go on to flip five heads in a row, i.e. the following coin flip is heads. In other words, in expectation, it takes two runs that start with four heads to achieve one run of five heads. Likewise, $E(R_{3+}) = 2 E(R_{4+}) = 4$, $E(R_{2+}) = 2 E(R_{3+}) = 8$, $E(R_{1+}) = 2 E(R_{2+}) = 16$, and $E(R_{0+}) = 2 E(R_{1+}) = 32$. The expected number of coin flips is $32 + 16 + 8 + 4 + 2 = 62$.

More generally, given a biased coin that comes up heads $p$ portion of the time, the expected number of flips to get $n$ heads in a row is $\frac{1}{p} + \frac{1}{p^2} + \ldots + \frac{1}{p^n} = \frac{1 - p^n}{p^n(1 - p)}$.

|cite|improve this answer
$\endgroup$
0
$\begingroup$

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

|cite|improve this answer
$\endgroup$
0
$\begingroup$

Use Markov chains. The nice part of Markov Chains is that they can be applied to a huge class of similar problems with relatively little thought (it's almost formulaic in application). It's also the most intuitive way to handle these problems.

(in Matlab code notation below)

%% setup full transition matrix with states from zero heads to 5 heads

T = $[ones(5,1)*.5,eye(5)*.5];$

$T = [T;zeros(1,6)]$

%%Take subset "Q" comprised of just transient states (5 heads is absorbing state) $Q = T(1:end-1,1:end-1);$

$M = inv(eye(5)-Q)$

absorbing Markov Chain has a similar example as this question BTW...

ans =

62
60
56
48
32

Where each row is the expected number of steps before being absorbed when starting in that transient state (0 through 4 heads, top to bottom).

|cite|improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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