Expected Number of coin flips for 2 consecutive heads for first time.

Question

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?

Answer 1

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

Answer 2

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, as 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 need another $4$ 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 and 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.

Answer 3

Let $X$ be the random variable denoting the number of times you have to flip the coin until there are two consecutive heads.

Flipping the coin twice, the possible outcomes are $HH, \ TH, \ HT$ and $TT$.

Thus, $\mathbb E[X]$ can be expressed as follows:

$\displaystyle \begin{aligned} \mathbb{E}[ X] = & \ \ 2 \\ & + p^{2} \cdotp \mathbb{E}[ HH|X]\\ & +p( 1-p) \cdotp \mathbb{E}[ TH|X]\\ & +p( 1-p) \cdotp \mathbb{E}[ HT|X]\\ & +( 1-p)^{2} \cdotp \mathbb{E}[ TT|X] \end{aligned}\tag*{}$

where $\mathbb E[A_1A_2\ldots A_n|X]$ denotes the expected value of how many more flips will be needed to obtain two consecutive heads after $A_1, \ A_2,\ \ldots,\ A_n$ have been outcomes of the first $n$ flips.

$\because$ You immediately stop after getting two consecutive heads, $\displaystyle \mathbb{E}[ HH|X] =0\tag{1}$

Again, $\mathbb{E}[ TH|X]$ can be expressed as follows based on the next outcome, $\displaystyle \begin{align*} & \ \mathbb{E}[ TH|X] \\ & =1+p\cdotp \mathbb{E}[ THH|X] +( 1-p) \cdotp \mathbb{E}[ THT|X]\\ & =1+p\cdot 0+( 1-p)\cdot\mathbb{E}[X]\\ &= 1+(1-p)\cdot \mathbb E[X]\tag{2} \end{align*}$

Getting a tail at any flip “restarts” the entire process of flipping so, it can be said that $\mathbb E[A_1A_2\ldots A_{n-1}T|X] = \mathbb E[X]$ such that no two consecutive $A_i$ and $A_{i+1}$ are heads (otherwise the process would stop there at $i+1$ only). This follows that: $\mathbb{E}[ HT|X] =\mathbb{E}[ X] \tag{3}$ $\displaystyle \mathbb{E}[ TT|X] =\mathbb{E}[ X]\tag{4}$

Substituting the results $(1)$, $(2)$, $(3)$ and $(4)$ in our expression of $\mathbb E[X]$, we have:

$\displaystyle \begin{aligned} \mathbb{E}[ X] = & \ \ 2\\ & +0\\ & +p( 1-p) \cdotp \{1+( 1-p)\cdot \mathbb{E}[ X]\}\\ & +p( 1-p) \cdotp \mathbb{E}[ X] \\ & +( 1-p)^{2} \cdotp \mathbb{E}[ X] \end{aligned}\tag*{}$

Solving this equation for $\mathbb E[X]$, we have:

$\color{orange}{\boxed{\mathbb{E}[ X] =\frac{p+1}{p^{2}}}}\tag*{}$

For a fair coin with $p=1/2$, $\mathbb E[X] = 6$.

Alternately, $\mathbb E[X] = 1+p\cdot \mathbb E[H|X]+(1-p) \cdot \mathbb E[T|X] \tag*{}$ $\\ \ $ $\begin{align}\mathbb E[H|X] &= 1+p\cdot\mathbb E[HH|X]+(1-p)\cdot\mathbb E[HT|X]\\ &= 1+(1-p)\cdot\mathbb E[X]\end{align}\tag*{}$ $\\ \ $ $\mathbb E[T|X]=\mathbb E[X]\tag*{}$ $\\ \ $ $\therefore\mathbb E[X] = 1+p\{1+(1-p)\mathbb E[X]\}+(1-p) \mathbb E[X]\tag*{}$ $\\ \ $ $ \implies \boxed{\mathbb E[X]=\frac{p+1}{p^2}}\tag*{}$

Answer 4

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