Number of expected flips for either HT or TH?

Question

So I was recently thinking about this interesting problem and wasn't sure how to tackle it. Let's say we are flipping some coins, and we are waiting for either $HT$ or $TH$, how many expected flips would it take to get either result?

As a followup, what if the probability of a heads on that coin is not, 0.5, but $p$?

---

Here's my approach, would love feedback:

For the simpler question when $p=0.5$: Let's say $X$ is the expected number of flips we will need to get either a $HT$ or $TH$, $A$ is the expected number of flips to get a single head, and $B$ is the expected number of flips to get a single tails. We know that $A=B=2$. We have a 50/50 chance to either flip a heads or a tail, in which case we want a tails after or a heads after, respectively.

So we have:

$X = \frac{1}{2} (1 + A) + \frac{1}{2} (1+B) = 3$

Is it that easy?

---

Extending it out for the generic case where we get a heads with probability $p$, we have:

$A = \frac{1}{p}$

$B = \frac{1}{1-p}$

so it's:

$X = p (1+A) + (1-p) (1 + B)$

$X = p (1+\frac{1}{p}) + (1-p) (1 + ( \frac{1}{1-p}))$

which simplifies to:

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

Is that correct?

Answer 1

My way of doing it:

If you already have flipped a heads, then you either are stopping after the next flip or else you will just return to the previous state due to flipping another heads. You do the first thing with probability $q$ and the second with probability $p$, so if $y$ is the expected number of flips after a H to get to HT then $y=q(1)+p(1+y)$ so $y=\frac{1}{1-p}=1/q$. In this branch you also needed to flip a heads at the beginning, so along this branch the expected total number of flips is $1+1/q$.

The probability of the branch in which the first flip was H is $p$ so its contribution to the total expectation is $p+p/q$. To get the contribution from the other branch (which terminates in TH) you can just exchange the roles of $p$ and $q$ so the total expectation is $p+p/q+q+q/p=1+\frac{p^2+q^2}{pq}$.

In the unbiased case this reduces to $3$, but in the biased case it's different, so something went awry in your biased calculation. Note that in the strongly biased case you expect the result to be approximately $1/\min \{ p,q \}$ because the typical flip sequence is a whole bunch of the more likely type followed by the less likely type.

Answer 2

You had the right idea, you just put the $A$ and $B$ in the wrong spots in your formula for $X$. The correct formula is

$$X=p(1+B)+(1-p)(1+A)=1+{p\over1-p}+{1-p\over p}={1\over p}+{1\over1-p}-1$$

Note, this passes the sanity check that $X=3$ for $p=1-p=1/2$. It also makes sense when $p\approx1$ or $p\approx0$, in which case(s) you expect it to take a long time to see a Tail if you're mostly getting Heads, or a Head if you're mostly getting Tails.