Expected number of coin tosses until $HH$ in a row I was asked the following problem:
Given a coin with $\displaystyle P( H) =p,\ P( T) =1-p$, what is the expected number of tosses until we receive two $\displaystyle H$ in a row?
I may use the fact that the expected number of tosses until the first $\displaystyle H$ is $\displaystyle \frac{1}{p}$.
My solution:
Let's denote $\displaystyle X_{2} =number\ of\ tosses\ until\ HH\ ( including\ the\ HH)$.
We want to find $\displaystyle E[ X_{2}]$.
At the same time, let's denote $\displaystyle X_{1} =number\ of\ tosses\ until\ H\ ( including\ H)$.
From the given we know that $\displaystyle E[ X_{1}] =\frac{1}{p}$.
Let's now try to simplify the expression $\displaystyle E[ X_{2}]$ with the Law of Total Probability.
Let's denote two events:
$\displaystyle A=after\ the\ 1^{st} \ H\ appears,\ the\ next\ toss\ is\ an\ H$.
$\displaystyle A^{c} =after\ the\ 1^{st} \ H\ appears,\ the\ next\ toss\ is\ a\ T$.
Let's also assume that the number of tosses until the first $\displaystyle H$ is some number $\displaystyle r$.
Since every toss is independent from each other, we know that $\displaystyle P( A) =P( H) =p$.
At the same, from the same reason, we will get $\displaystyle P\left( A^{c}\right) =P( T) =1-p$.
From the \ Law of Total Probability then, we can define:
$\displaystyle E[ X_{2}] =P( A) \cdotp E[ X|A] +P\left( A^{c}\right) \cdotp E\left[ X|A^{c}\right]$.
$\displaystyle =p\cdotp E[ X|A] +( 1-p) \cdotp E\left[ X|A^{c}\right]$.
But,
• $\displaystyle E[ X|A]$ = the expected number of tosses until the first HH, if we know that we had exactly $\displaystyle r$ tosses until the first $\displaystyle H$, and after that we had an $\displaystyle H$.
Basically, this means we received $\displaystyle HH$ consecutively for the first time! So we will stop tossing here.
The number of tosses, in this case, will be is $\displaystyle r+1$.
We know the expected value of $\displaystyle r$ is $\displaystyle E[ X_{1}] =\frac{1}{p}$.
So: $\displaystyle E[ X|A] =\frac{1}{p} +1$.
• $\displaystyle E\left[ X|A^{c}\right]$ = the expected number of tosses, if we know that we had exaclty $\displaystyle r$ tosses until the first $\displaystyle H$, and after that we had a $\displaystyle T$.
Also, in this case, we tossed the coin $\displaystyle r+1$ times, but we won't be stopping, since we didn't achieve the $\displaystyle HH$ consecutively. The opposite, we are left facing the same problem recursively. Each toss is independent from the previous one, so after the $\displaystyle r+1$, we have to "start over", and have again $\displaystyle E[ X_{2}]$ expected tosses.
So: $\displaystyle E\left[ X|A^{c}\right] =\frac{1}{p} +1+E[ X_{2}]$.
Overall plugging into our initial equation we get:
$\displaystyle  \begin{array}{{>{\displaystyle}l}}
E[ X_{2}] =p\cdotp \left(\frac{1}{p} +1\right) +( 1-p) \cdotp \left(\frac{1}{p} +1+E[ X_{2}]\right)\\
=1+p+\frac{1}{p} +1+E[ X_{2}] -1-p\cdotp E[ X_{2}]\\
\Rightarrow \\
p\cdotp E[ X_{2}] =\frac{1}{p} +1\\
\Rightarrow \\
E[ X_{2}] =\frac{1+p}{p^{2}} .
\end{array}$
I'm confident this solution is correct, by looking at this other question: Expected value of number of trials to get k SUCCESSIVE successes.
I basically plugged in my numbers into their solution.
Despite this, they used a different method it seems in the first passage, which I don't really understand where it's derived. At the same time, I feel like my answers use a lot of words especially for the cases of $\displaystyle E[ X|A] ,\ E\left[ X|A^{c}\right]$. I hoped to have some formula to use instead of having to explain the solution "logically".
Any advice?
 A: Best to solve this sort of thing via states.  There are $3$ states we care about, labeled by the portion of $HH$ we have going.  The states are $\emptyset, H, HH$.  We start in $\emptyset$.  For a state $S$ let $E_S$ denote the expected number of tries it will take to get to $HH$. We want $E_{\emptyset}$ Of course $E_{HH}=0$.
We remark that state $\emptyset$ either goes to $H$ (prob. $p$) or stays in $\emptyset$ (prob. $1-p$).  Thus $$E_{\emptyset}=p\times E_H+(1-p)\times E_{\emptyset}+1$$
Similarly $$E_H=p\times 0 + (1-p)\times E_{\emptyset}+1$$
which quickly implies that $$E_{\emptyset}=\frac {1+p}{p^2}$$
as desired.
As a variant:  Consider the possible initial sequences.  Only three starts are possible:  Either you get $T$ initially, in which case the game restarts after $1$, or you get $HT$ in which case the game restarts after $2$, or you get $HH$ in which case the game is over in $2$.  Thus $$E=(1-p)\times (E+1)+p(1-p)\times (E+2)+p^2\times 2\implies E=\frac {1+p}{p^2}$$
Note:  as the question of finiteness was raised, it is not terribly difficult to resolve it.  Consider the "coarser" problem in which you toss the con twice at a time and require that you get the $HH$ in a single turn.  That has an expectaion of $\frac 1{p^2}$ so the expected value of the current game must be $≤\frac {2}{p^2}$.  (Of course, if $p=0$ none of these quantities are finite).
