2
$\begingroup$

I was working on problems on expectation and found this one as a question from a well-known exam

Assume that you are flipping a fair coin, i.e. probability of heads or tails is equal. Then the expected number of coin flips required to obtain two consecutive heads for the first time is.

(A)4

(B)3

(C)6

(D)10

(E)5

I worked up like Let N be the number of tosses required untill 2 consecutive heads are obtained for the first time.

Let the probability of obtaining heads be p and tails be q and for a coin p=q=1-p=1-q.

For N=2, the probability will be $p^2$

For N=3, the probability will be $p^2.q$

For N=4, the probability will be $q^2.p^2$

For N=5, the probability will be $q^3.p^2$

and so on...

Now, $E[N]=2(p^2)+3(p^2.q)+4(q^2.p^2)+5(q^3.p^2)+......$

and this comes out to be $\frac{3}{2}$ but it matches with none of the options.

Please tell me where I am wrong and what should I do to reach the correct solution?

$\endgroup$
  • $\begingroup$ The probability for $n=4$ is actually $q^2p^2+qp^3$ You have overlooked the sequence HTHH. You have made a similar mistake for $n>4.$ $\endgroup$ – saulspatz Jul 9 '18 at 4:00
  • $\begingroup$ One way to do this is with Markov chains. Do you know about Markov chains? $\endgroup$ – saulspatz Jul 9 '18 at 4:07
  • $\begingroup$ @Saulpatz-no I don't know about it $\endgroup$ – user3767495 Jul 9 '18 at 4:08
  • $\begingroup$ Okay, there are other ways, but it will take me a bit longer to work out :-) $\endgroup$ – saulspatz Jul 9 '18 at 4:10
  • $\begingroup$ @Saulpatx-I could have read about markov chains, but since I am preparing for a competitive exam, I have to stick to the syllabus and Markov chain is not there in it :( $\endgroup$ – user3767495 Jul 9 '18 at 4:20
2
$\begingroup$

As long as the game is not over, we are in one of two states. In what I'll call state $1$, we have just tossed a head, so if we get another head on the next toss, the game is over. If the game is not over, and we are not in state $1$, then I'll say we are in state $2$. We need to toss two consecutive heads to finish the game. We are in state $2$ at the beginning of the game, of if we have just tossed tails.

The complication is that when we toss the coin, we may switch states. Let $a$ be the expected number number of tosses required in the future if the are in state $2$, and let $b$ be the expected number of tosses required in the future if we are in state $1$. We need to see how $a$ and $b$ are related.

Suppose we are in state $1$, so that the last toss was a head, but we still need another head to end the game. We have to toss the coin at least once. Half the time, that comes up heads and the game is over. But half the time, the coin comes up tails, and we are in state $2$. In that case, we expect to need $a$ more tosses to end the game. That is, $b$ the number of tosses needed if we are in state $1$ is 1+$a/2.$

Similarly, if we are in state $2$, we always need to toss the coin once. The number of tosses we need after that depends on what happens of course. Half the time it's tails, and we stay in state $2$, but half the time it's heads, and we move to state $1$. So after the obligatory initial toss, we will need $(a+b)/2$ more tosses, on average.

We have $$ \begin{align} a &= 1 +\frac12(a+b)\\ b &= 1 + \frac12a \end{align}$$

Solving gives $\boxed{a=6, b=4}$ $6$ is the answer, since when the game starts, the "last toss" was certainly not a head.

If you still don't see it, it might help you to imagine that the game actually takes the expected number of tosses. This may give you a feel for what's going on. Suppose we are at the start of the game. We toss the coin, and heads comes up so we another $5$ tosses, making $5$ in all. Half the time, it's tails and we need another $6$ tosses, so $7$ in all. On average, we need $(5+7)/2=6$. Suppose we are in state $1$. Half the time, we get heads an the game is over after one toss, but half the time, we get tails, and we need $7$ tosses in all. On average, we need $(1+7)/2=4$ tosses.

If you still don't see it, it might help you to carry these calculations out further with a probability tree. Just figure out when the game keeps going and when it stops, and at some point stick $4$ and $6$ at the appropriate places. When you calculate the expected number of moves at the base of the tree, you'll always get $4$ or $6$, depending on what state you're in -- if you don't make any mistakes.

EDIT

Strictly speaking, this argument only shows that if the expectation exists, then its value is $6.$ Of course, that doesn't matter on a multiple choice exam.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ @saulpatz-Sorry to say, but I still didn't got the equations :( . I am weak at math $\endgroup$ – user3767495 Jul 9 '18 at 5:45
  • $\begingroup$ I'll try to make my explanation plainer. Bear with me for a few minutes. $\endgroup$ – saulspatz Jul 9 '18 at 5:47
2
$\begingroup$

Here is a generating function approach.


$T$ is represented by $(1-p)x$
$HT$ is represented by $p(1-p)x^2$
$HH$ is represented by $p^2x^2$


The generating function for the probability that it will take $n$ flips to get two heads in a row is $$ \begin{align} g(x) &=p^2x^2\sum_{k=0}^\infty\left((1-p)x+p(1-p)x^2\right)^k\\ &=\frac{p^2x^2}{1-(1-p)x(1+px)}\tag1 \end{align} $$ As a check, $$ g(1)=1\tag2 $$ that is, the probability of eventually getting two heads is $1$.


Taking the derivative of $(1)$: $$ g'(x)=\frac{p^2x\,(2-(1-p)x)}{\left(1-(1-p)x(1+px)\right)^2}\tag3 $$ Thus, the expected number of flips to get two heads in a row is $$ g'(1)=\frac{1+p}{p^2}\tag4 $$ For a fair coin, we get the expected number of flips to get two heads in a row is $$ \begin{align} \frac{1+p}{p^2} &=\frac{\ \frac32\ }{\frac14}\\[6pt] &=6\tag5 \end{align} $$


Taking two derivatives of $(1)$: $$ g''(x)=\frac{2p^2\left(1+p(1-p)x^2(3-(1-p)x)\right)}{\left(1-(1-p)x(1+px)\right)^3}\tag6 $$ Thus, the variance of the number of flips to get two heads in a row is $$ g''(1)+g'(1)-g'(1)^2=\frac{(1-p)(1+p(3+p))}{p^4}\tag7 $$ For a fair coin, we get the variance of the number of flips to get two heads in a row is $$ \begin{align} \frac{(1-p)(1+p(3+p))}{p^4} &=\frac{\ \frac{11}8\ }{\frac1{16}}\\[6pt] &=22\tag8 \end{align} $$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Could you please detail why the equation for the variance is $g''(1)+g'(1)-g'(1)^2$? I guess it comes from $Var(X)=E(X-E(X))^2$, but I can't fully follow it $\endgroup$ – David Aug 6 at 15:57
  • 1
    $\begingroup$ Note that $\color{#C00}{E(X)}$ is treated as a constant in the computation below $$\begin{align}\mathrm{Var}(X) &=E\!\left((X-\color{#C00}{E(X)})^2\right)\\ &=E\!\left(X^2-2X\color{#C00}{E(X)}+\color{#C00}{E(X)}^2\right)\\ &=E\!\left(X^2\right)-2E(X)\color{#C00}{E(X)}+\color{#C00}{E(X)}^2\\ &=E\!\left(X^2\right)-E(X)^2\end{align}$$ $\endgroup$ – robjohn Aug 6 at 16:34
  • 1
    $\begingroup$ The generating function for the probability that it will take exactly $n$ flips to get two heads in a row is $$g(x)=\sum_{n=0}^\infty p(n)x^n$$ Note that $g(1)=\sum\limits_{n=0}^\infty p(n)=1$ since $p(n)$ is a probability distribution. $$g'(x)=\sum_{n=0}^\infty np(n)x^{n-1}$$ So $g'(1)=\sum\limits_{n=0}^\infty np(n)=E(n)$. $$g''(x)=\sum_{n=0}^\infty n(n-1)p(n)x^{n-2}$$ So $g''(1)=\sum\limits_{n=0}^\infty n(n-1)p(n)=E\!\left(n^2\right)-E(n)$. Thus, the variance is $$E\!\left(n^2\right)-E(n)^2=g''(1)+g'(1)-g'(1)^2$$ $\endgroup$ – robjohn Aug 6 at 16:34
0
$\begingroup$

Let $A$ be the event that we get two consecutive heads for the first time. $$E(A)=\frac{1}{2}\left(E(A/First\ toss\ was\ a\ tail)+1\right)+\frac{1}{2}\left(\frac{1}{2}\left(E(A/Second\ toss\ was\ a\ tail)+2\right)+\frac{1}{2}*2\right)$$

Now, $E(A/First\ Toss\ was\ a\ tail)=E(A/Second\ toss\ was\ a\ tail)=E(A)$, because getting a tail puts us back on square one, and we have to 'start over'

Hence, $$E(A)=\frac{1}{2}\left(E(A)+1\right)+\frac{1}{2}\left(\frac{1}{2}\left(E(A)+2\right)+\frac{1}{2}*2\right)$$

$$E(A)=6$$

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