Suppose you flip a fair coin repeatedly until you see a Heads followed by a Tails. What is the expected number of coin flips you have to flip?

By manipulating an equation based on the result of the first flip, shown at this link:

http://www.codechef.com/wiki/tutorial-expectation

the answer is 6. This also makes sense intuitively since the expected value of the number flips until HH or TT is 3. But is there a way to tackle this problem by summing a series of probabilities multiplied by the values?

Thank you!

  • @AndréNicolas Well, not the main way, but using that method. I'll edit the post. – Dhruv Oct 10 '13 at 6:42
up vote 8 down vote accepted

Consider the string of tosses that precede the first HT. If there is ever an H in that string, every toss after that (but within the string) must also be H. Thus, if there are $m$ tosses before the first HT, they must take the form $T^kH^{m-k}$ for some $k\in\{0,\ldots,m\}$. There are therefore exactly $m+1$ possibilities for this initial string of length $m$. If the first HT is completed on toss $n$, then $m=n-2$, and there are $n-1$ possibilities for the initial string, each occurring with probability $\left(\frac12\right)^{n-2}$, assuming a fair coin. The total probability of completing the first HT on toss $n$ is therefore $(n-1)\left(\frac12\right)^n$, and you want

$$\sum_{n\ge 2}n(n-1)\left(\frac12\right)^n\;.$$

If $f(x)=\frac1{1-x}$, for $|x|<1$ we have $f(x)=\sum_{n\ge 0}x^n$, so

$$\frac1{(1-x)^2}=f\,'(x)=\sum_{n\ge 1}nx^{n-1}\;.$$

Now differentiate again and multiply by $x^2$:

$$\frac{2x^2}{(1-x)^3}=x^2f''(x)=\sum_{n\ge 2}n(n-1)x^n\;.$$


Note that the answer is not $6$; you must have misapplied the method from the link. Let $x$ be the expected number of tosses, and let $y$ be the expected additional number of tosses if you have just thrown H. Then

$$x=\frac12(x+1)+\frac12(y+1)\;,$$

and

$$y=\frac12+\frac12(y+1)\;.$$

Then $y=2$, so $x=\frac12(x+1)+\frac12(3)=\frac{x}2+2$, and $x=4$.

  • Thank you, I just realized that by solving the derivative, this was very helpful! – Dhruv Oct 10 '13 at 7:42
  • @Dhruv: You’re welcome! – Brian M. Scott Oct 10 '13 at 7:43
  • 1
    $6$ would be correct if the pattern sought was HH (and similarly if it was TT), but not HT, or TH – Henry Oct 10 '13 at 10:43

Let X be the random variable which counts the number of flips till we get a T (tails). Then: $$E[X] = \frac{1}{2}\cdot1 + \frac{1}{2}(1+E[X])$$ $$\implies E[X] = 2$$ The first term on LHS is if we get a T on a our first flip (with probability $\frac{1}{2}$). The second term is if we get a H (heads) on our first flip (with probability $\frac{1}{2}$), which means that we are effectively starting over with 1 extra flip.

Now let Y be the random variable which counts the number of flips till we get a HT sequence. Then: $$E[Y] = \frac{1}{2}(1+E[Y])+\frac{1}{2}(1+E[X])$$ $$\implies E[Y] = 4$$ The first term on LHS is if we get a T on our first flip (with probability $\frac{1}{2}$), which means we are effectively starting over with 1 extra flip. The second term if we get a H on our first flip (with probability $\frac{1}{2}$), then all we want is a T, which means we want to count 1 + expected number of flips to get a T.

  • I am quite new here, but what is LHS? – user152503 Apr 3 at 20:34
  • @user152503 LHS stands for the left-hand side (of the equation) – user7610 Apr 4 at 21:56

Another way to solve this is to use Markov chains. Let state 0 be the start state. Then with probability 0.5 you will get heads and move to state 1; with probability 0.5 you will get tails and stay in state 0. Once in state 1, you will either get heads (probability 0.5) and remain in state 1 or you will get tails (probability 0.5) and move to state 2 which is the accepting state.

As a transition matrix then, we have:

$$ \begin{array}{c|ccc} & 0 & 1 & 2 \\ \hline 0 & 0.5 & 0.5 & 0 \\ 1 & 0 & 0.5 & 0.5 \\ 2 & 0 & 0 & 1 \\ \end{array} $$

If we let $\phi(i)$ be the expected number of flips to go from state $i$ to state 2, then from this transition matrix we must have:

$\phi(0) = 0.5*(1 + \phi(0)) + 0.5*(1+\phi(1)) + 0*(1+\phi(2))$ $\phi(1) = 0*(1 + \phi(0)) + 0.5*(1+\phi(1)) + 0.5*(1+\phi(2))$ $\phi(2) = 0*(1 + \phi(0)) + 0*(1+\phi(1)) + 1*\phi(2)$

So, obviously, $\phi(2)=0$ and plugging this into the first two equations gives the same system to solve as in the other answers.

Solving for $\phi(0)$ gives $\phi(0) = 4$.

"Why" does this only require 4 flips in expectation making it different than the 6 flips needed in expectation to see HH or TT? If the coin is fair, then out of a two flip sequence, HH, HT, TH, and TT are all equally likely, so shouldn't it take the same amount of "time" before you expect to see any given one of those two-flip patterns?

No. Firstly because we just calculated it and the expectations are different. Unless our model of the situation is wrong, then 4 is simply the answer, even if it doesn't "feel" right. Secondly, though, there is an important asymmetry in the two problems.

When looking for HH, we would have a transition matrix like this:

$$ \begin{array}{c|ccc} & 0 & 1 & 2 \\ \hline 0 & 0.5 & 0.5 & 0 \\ 1 & 0.5 & 0 & 0.5 \\ 2 & 0 & 0 & 1 \\ \end{array} $$

The difference is the second row. Instead of being able to stick around indefinitely in state 1, we are immediately faced with either succeeding (getting that second H) or failing and being forced to start over.

This means, on average, it should take longer in the HH case to reach the success state 2 from the middle state 1 than in our original problem. But the probability of going from the start state 0 to the middle state 1 remains identical between the two problems.

So we should expect that it takes longer on average to see the first HH than to see the first HT.

An interesting exercise would be to ask: is there a biased coin of some kind for which the expected number of flips to see HH is the same as the expected number of flips to see HT?

I decided to go ahead and work this one out assuming that $p$ represents the probability of the coin landing on Heads on a certain flip. You can modify the above two transition matrices to use $p$ and $1-p$ in the appropriate places, get the system of equations in each case (the HH case or the HT case) and then solve.

When I solve this, I get that in general, for a coin with bias $p$ for Heads, it will take on average $1/p + 1/(1-p)$ flips to see HT (this agrees with the answer in the 0.5 case) and it will take $(1+p)/p^2$ flips in the HH case, again agreeing with previous calculations for the 0.5 case.

This leads to an equation for $p$:

$\frac{1}{p} + \frac{1}{1-p} = \frac{1+p}{p^2}$

and after rearranging and simplifying, it is a polynomial equation:

$0 = 1 - p - p^2$

which has roots: 0.61803399, -1.618003399, the first of which can serve as a valid bias parameter for a coin.

Thus, if you ever encounter a coin with a probability of Heads of 0.61803399, then in that case it will be true that, on average, it takes as many flips to see the first occurrence of HH as it does to the first occurrence of HT.

  • Hello, when you calculate how many steps, in first two equations, you use $1+\phi(2)$, but in the third one you only use $\phi(2)$, can you explain why? – Xiaonan Aug 17 '16 at 2:27
  • @Xiaonan In the equation for $\phi(2)$, the expected number of steps to get to state 2 is 0 (because you are already in state 2). This means if you are in state 2, then with probability of 1, you will stay in state 2 and you will not have any additional flips to get there. This is why there is not an extra $1$ added, but in the earlier equations you would represent the need to perform a flip before making it into state 2, by adding 1. You don't need to count the work of that flip in the final equation, because the flip itself is not needed to achieve state 2 (you are already in state 2). – ely May 4 at 14:43

Here is another way of thinking about it: condition on the location of the 1st Head and use the law of total expectation (tower rule).

Let $N$ be the number of throws for getting the first HT. Let $Z$ be the location of the first H. Then, by the tower rule:

$$ E[N] = E[E[N|X]] = \Sigma_{k = 1}^{\infty} E[N | Z = k] P(Z = k)$$.

Let us compute each of these separately. The easy one first: $P(Z = k) = p q^{k-1}$, since this is the probability of getting the first H on throw $k$ with all $(k-1)$ throws before it being T's.

The $E[N|X=k]$ term is a bit more tricky... but the recursion is nice. It is the expected number of turns to get a HT given the $k^{th}$ turn yields the first H. Clearly, if the $k^{th}$ turn yields a H, we have another $N-k$ turns on average, starting from H, to get the required result.

Now, if the $k^{th}$ throw is a H, the $(k + 1)^{th}$ throw is either a H or a T. If it a T (with probability $q$), we are done, and it took $(k+1)$ turns. If it is a H (with probability $p$), we have used up $(k+1)$ turns and we have another $E[N|Z = k] - k $ turns to go. This yields the recursion:

$$E[N|Z = k] = q(k + 1) + p(k + 1 + E[N|Z = k] - k) $$.

Solving, we get $E[N|Z=k] = 1/q + k$.

Substituting all these back and doing the summations, we get:

$$E[N] = \frac{1}{p} + \frac{1}{q}.$$

For $p = q = 1/2$, E[N] is 4.

Your expected number of flips is a random variable which I will call $W$ for "waiting time"; you want to find the expectation $E[W]$.

Let's break up the process into two stages ("divide and conquer"). You start by flipping the coin repeatedly until it comes up heads; after the first head is sighted, you go on flipping until it comes up tails. So $W=X+Y$, where $X$ is the number of flips up to and including the first head, and $Y$ is the number of additional flips until the coin comes up tails. By the linearity of expectation, $E[W]=E[X+Y]=E[X]+E[Y]$. Moreover, it's clear that $E[Y]=E[X]$, because the second stage is just like the first stage, with heads and tails interchanged. So $E[W]=2E[X]$.

Finding $E[X]$ is an easier problem, which you may have already done, so you know that $E[X]=2$; in that case you just quote the earlier result and conclude that $E[W]=4$. Otherwise, you can find $E[X]$ by using "indicator variables". Namely, let $X_n$ be the random variable which takes the value $1$ if $X\gt n$ (i.e. the first $n$ flips come up tails) and $0$ otherwise. Since $X_n$ is a Bernoulli variable, $E[X_n]=P(X_n=1)=(\frac12)^n$. Since $X=1+X_1+X_2+X_2+\cdots$, it follows by linearity that $$E[X]=1+E[X_1]+E[X_2]+E[X_3]+\cdots=1+\frac12+\frac14+\frac18+\cdots=2.$$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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