Expected number of coin flips to see $3$ heads

Question

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?

Answer 1

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

Answer 2

Hint: Assume you get 3 heads in k turns , at last you always get head and in k-1 turns some where you get 2 heads. Expectation is

$$\sum_{k=3}^{\infty}\binom{k-1}{2}.{1 \over 2^k} .k$$

Answer 3

Hint: After $n-1$ tosses we need to see $2$ heads and $n-1-2=n-3$ tails.

The probability for that is $\binom{n-1}{2}\cdot 0.5^2\cdot 0.5^{n-3}$. The last toss must be head. Thus the probability to get 3 heads after n tosses is

$$P(X=3)=\binom{n-1}{2}\cdot 0.5^2\cdot 0.5^{n-3}\cdot 0.5=\binom{n-1}{2}\cdot 0.5^n$$

Now calculate the expected value.

$$\mathbb E(X)=\sum_{n=3}^{\infty} n\cdot \binom{n-1}{2}\cdot 0.5^n$$

Remark

If you have problems to calculate the sum see the answer here $(k=3)$ from Arash.