[Math] Expected number of coin flips to see $3$ heads

expected valueprobabilityprobability theory

You toss a coin until you see $3$ (not necessarily consecutive heads).
What's the expected number of coin tosses you make?


I tried a lot of things, and I've seen the solution for three consecutive heads, but I'm not so sure how to do it if they are non-consecutive.

With probability $1/8$, we stop after the first three coin tosses (if we get HHH).

With probability $3/16$, we will terminate after the first four coin tosses (we can get THHH, HTHH, HHTH).

It gets really messy for the rest of them, and so I don't think this approach is quite correct. Can anyone please help me solve this problem?

Best Answer

No need for infinite sums here, the answer is just $3\times E_1=6$. More broadly, the expected number for $n$ Heads is $2n$.

To see this, let $E_n$ be the expected number of tosses for $n$ Heads. We note that, to see $n$ Heads requires that you first see $n-1$, which you expect to take $E_{n-1}$ tosses. Then you need to see one more, which you expect to take $E_1$ tosses. Thus we have the recursion $$E_n=E_{n-1}+E_1$$

It follows, inductively, that $$E_n=n\times E_1$$

Since $E_1=2$ the claim follows.

For completeness, here is a proof that $E_1=2$:

Consider the first toss. Either it is $H$ or $T$. If it is $H$, you stop. If it is $T$ you restart (but you've added $1$ to the count). Thus $$E_1=\frac 12\times 1+\frac 12\times (E_1+1)\implies E_1=2$$

May be worth remarking that this gives another approach to the original question. Say we want to compute $E_n$. Then we consider one toss. Either it is $H$, in which case you want $E_{n-1}+1$ or it is $T$ in which case you want $E_n+1$. Thus $$E_n=\frac 12\times (E_{n-1}+1)+\frac 12\times (E_n+1)\implies E_n=E_{n-1}+2$$