Stuck on a probability problem/Expectation of coin toss

Question

I'm stuck on the following problem that is due for tomorrow:

We're flipping 1 coin indefinitely. $X$ is a random variable that count the amount of coin tosses. What is the expectation of the number of coin toss until we have the following sequence: THH (T: tail, H: head)

We know that TTT has an expectation of 14.

Edit: Someone told me that

$E[X]= 3 + P[X>3]E[X].$

$P[X>3]=(1 - (1/8))$

$E[X]=24$

But I have now idea how to get to the last step?

Answer 1

Generating Function Approach

Duration Until $\boldsymbol{THH}$

Any trial can uniquely be constructed from any number of $H$ atoms, then an arbitrary combination of $TH$ and $T$ atoms, then a $THH$ atom. Put this together in a generating function: $$ \begin{align} \overbrace{\ \ \frac1{1-x}\ \ }^\text{$H$ atoms}\overbrace{\frac1{1-x-x^2}}^\text{$TH$, $T$ atoms}\overbrace{\quad\ x^3\quad\ \vphantom{\frac11}}^\text{$THH$ atom} &=\frac{x^3}{1-2x+x^3} \end{align} $$ The expected duration is then $$ \begin{align} \left.x\frac{\mathrm{d}}{\mathrm{d}x}\frac{x^3}{1-2x+x^3}\right|_{x=\frac12} &=\left.\frac{x^3(3-4x)}{\left(1-2x+x^3\right)^2}\right|_{x=\frac12}\\[9pt] &=8 \end{align} $$

---

Duration Until $\boldsymbol{THT}$

Any trial can be uniquely constructed from any number of $H$ atoms, then an arbitrary combination of $T$ and $TH^n$ atoms for $n\ge2$, then a $THT$ atom. Put this together in a generating function: $$ \overbrace{\ \ \frac1{1-x}\ \ }^\text{$H$ atoms}\overbrace{\frac1{1-x-\frac{x^3}{1-x}}}^\text{$T$, $TH^n$ atoms}\overbrace{\quad\ x^3\quad\ \vphantom{\frac11}}^\text{$THT$ atom}=\frac{x^3}{1-2x+x^2-x^3} $$ The expected duration is then $$ \begin{align} \left.x\frac{\mathrm{d}}{\mathrm{d}x}\frac{x^3}{1-2x+x^2-x^3}\right|_{x=\frac12} &=\left.\frac{x^3\left(3-4x+x^2\right)}{\left(1-2x+x^2-x^3\right)^2}\right|_{x=\frac12}\\[9pt] &=10 \end{align} $$

---

Duration Until $\boldsymbol{TTT}$

Any trial can be uniquely constructed from any number of $H$, $TH$, and $TTH$ atoms, then an $TTT$ atom. Put this together in a generating function: $$ \overbrace{\frac1{1-x-x^2-x^3}}^\text{$H$, $TH$, and $TTH$ atoms}\overbrace{\quad\ x^3\quad\ \vphantom{\frac11}}^\text{$TTT$ atom}=\frac{x^3}{1-x-x^2-x^3} $$ The expected duration is then $$ \begin{align} \left.x\frac{\mathrm{d}}{\mathrm{d}x}\frac{x^3}{1-x-x^2-x^3}\right|_{x=\frac12} &=\left.\frac{x^3\left(3-2x-x^2\right)}{\left(1-x-x^2-x^3\right)^2}\right|_{x=\frac12}\\[9pt] &=14 \end{align} $$

Answer 2

Your edit is not quite right and gives the wrong answer.

For a pattern like TTH, you could consider $E[X_{TT}]$ as the expected remaining number of flips if the last two were TT, $E[X_{TT}]$ if the last one was T but the last two were not TT, and $E[X]$ if the last was not T and the last three were not TTH. Since you must now flip a coin and get heads or tails, you can say

• $E[X_{TT}] = 1 + \frac12 \times 0 + \frac12 \times E[X_{TT}]$
• $E[X_{T}] = 1 + \frac12 \times E[X] + \frac12 \times E[X_{TT}]$
• $E[X] = 1 + \frac12 \times E[X] + \frac12 \times E[X_{T}]$

so three equations in three unknowns. The solutions are thus $E[X_{TT}]=2$ and $E[X_{T}]=6$ and $E[X]=8$ and you want the last of these