$\begingroup$

I have a fair coin. What is the expected number of tosses to get three Heads in a row?

I have looked at similar past questions such as Expected Number of Coin Tosses to Get Five Consecutive Heads but I find the proof there is at the intuitive, not at the rigorous level there: the use of the "recursive" element is not justified. The Expectation $\mathbb E[X]$ is a number, not a random variable, as it is treated there. Please make this clear.

$\endgroup$ 3

2 Answers

$\begingroup$

Consider the outomes $T,HT,HHT,HHH$. All but the last put you back to the start. So if $x$ is the expected number of tosses to get HHH we have $$x=\frac{1}{2}(x+1)+\frac{1}{4}(x+2)+\frac{1}{8}(x+3)+\frac{1}{8}3\ \ (*)$$ That is easy to solve for $x$ giving $$x=14$$

---------- Added 26 June 2016 ----------

Now let us consider this solution more carefully. Note first that the events $T,HT,HHT,HHH$ are disjoint and exhaustive. They have probabilities $\frac{1}{2},\frac{1}{4},\frac{1}{8},\frac{1}{8}$ respectively.

Let $3H$ be the random variable "a number of tosses until the first run of three $H$ is achieved". Now $(*)$ states: $$E(3H)=E(3H|T)p(T)+E(3H|HT)p(HT)+E(3H|HHT)p(HHT)+E(3H|HHH)p(HHH)$$ This is sometimes known as "computing expectations by conditioning" (see, for example, Sheldon Ross, Introduction to Probability Models 3.4 p100). It is often written more concisely as $$E(E(X|Y))=E(X)$$ where the outer expectation on the LHS is $E_Y(\cdot)$.

---Added 5-2-2022---

The expected number of tosses to obtain three consecutive heads given that the first toss is a tail equals one plus the expected number of tosses to obtain three consecutive heads (starting from that point). $$\mathsf E(3H\mid T) = 1+\mathsf E(3H)$$

This is the $(1+x)$ factor in the above. So too are the other terms evaluated.

---

It follows directly from the definitions of conditional probability and expectation. The discrete case is particularly straightforward.

It just comes down to what is sometimes called the "partition theorem": if $B_n$ is a partition of the sample space, then $E(X)=\sum_nE(X|B_n)p(B_n)$. Note that we have $$E(X|Y=y)=\sum_xxp(X=x|Y=y)=\sum_xx\frac{p(X=x\cap Y=y)}{p(Y=y)}$$ where the last equality is just the definition $$p(A|B)=\frac{p(A\cap B)}{p(B)}$$Having written all that, I see that Wikipedia calls it the "Law of total expectation" and has an excellent article on it.

$\endgroup$ 20 $\begingroup$

Although the question has already been answered, I would like to offer a very similar solution but a different approach mindset to it.

It is a crude image but it essentially explains the answer above very beautifully.

At the beginning, we have no coins tossed so we have no consecutive heads. Next, we toss an $H$ or $T$ with probability $\frac{1}{2}$. Thus, we go the next state $2$ with probability $\frac{1}{2}$, similarly with $3$ and $4$.

Let $g(x)$ be the expected time until we reach state $4$, $HHH$, from state $x\in\{1,2,3,4\}$. Obviously $g(4)=0$ since we are already at state $4$!

\begin{align} g(1)&=\frac{1}{2}(g(2)+g(1))+1\\ g(2)&=\frac{1}{2}(g(3)+g(1))+1\\ g(3)&=\frac{1}{2}(g(4)+g(1))+1\\ \end{align}

Since whenever we move from one state to another we take or "waste" one step. However, we only take a step in the correct direction with probability $\frac{1}{2}$. Otherwise, we have to go back to state $1$ and need to find $g(1)$.

Thus, by substitution (or recursion), $$g(1)=1+\frac{1}{2}g(1)+\frac{1}{2}\left(\frac{1}{2}g(3)+\frac{1}{2}g(1)+1\right)=1+\frac{1}{2}g(1)+\frac{1}{4}g(1)+\frac{1}{2}+\frac{1}{4}\left(\frac{1}{2}g(1)+1\right)=1+\frac{1}{2}+\frac{1}{4}+g(1)\left(\frac{1}{2}+\frac{1}{4}+\frac{1}{8}\right)$$

$$g(1)=14$$

$\endgroup$ 2