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

closed as off-topic by Did, C. Falcon, Shailesh, Leucippus, Daniel W. Farlow Jun 26 '16 at 3:11

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – Did, C. Falcon, Shailesh, Leucippus, Daniel W. Farlow
If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ that is precisely one of those not completely clear kind of proofs I was referring to. $\endgroup$ – RandomGuy Jun 25 '16 at 18:22
  • $\begingroup$ I understand how to apply the argument there to the case $n=3$, that is trivial... :D what is unclear to me is the justification of this "taking the expectation recursively" that I found unclear and I want to see a rigorous justification of this step. That in the solution you linked is not given. $\endgroup$ – RandomGuy Jun 25 '16 at 18:26
  • $\begingroup$ I think you didn't understand my point $\endgroup$ – RandomGuy Jun 25 '16 at 18:31
16
$\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)$.

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$
  • 4
    $\begingroup$ I know this isn't quite related, but congrats on 10k reputation! $\endgroup$ – Noble Mushtak Jun 25 '16 at 18:24
  • $\begingroup$ Thanks! I am now absolutely mystified as to how people have managed to get to 200k in the few years MSE has been around! $\endgroup$ – almagest Jun 25 '16 at 18:25
  • $\begingroup$ Please read my comment above. Yes, I understand how to apply that method to this situation. The unclear thing is the justification of the recursive relation on the expectation. That in the link is not provided. $\endgroup$ – RandomGuy Jun 25 '16 at 18:28
  • $\begingroup$ I will try to better explain myself. I understand your argument, but this is an intuitive explanation as long as you are not using properties of the expectation which allow you to PROVE that you can indeed use the recursive equation. THat is my point: intuitively is clear what you say, but it is not a rigorous proof as long as you show that it depends on the properties of the expectation of the random variable considered here. $\endgroup$ – RandomGuy Jun 25 '16 at 18:34
  • 2
    $\begingroup$ Why is TT not considered? $\endgroup$ – Jaydev Jul 24 '17 at 1:22
8
$\begingroup$

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

enter image description here

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$

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