Why is the expected number coin tosses to get $HTH$ is $10$?

Solution 1:

Denote the state before tossing $\emptyset$, you start in it. If your first toss is $H$, you proceed to the next state, otherwise stay in $\emptyset$. From state $1$ there's no way back to state $\emptyset$, but if you toss $H$ you stay in state 1 (since you need $HTH$). You should get something like

$\mathbf{P} = \begin{bmatrix}\frac{1}{2} & \frac{1}{2} & 0 & 0\\0 & \frac{1}{2} & \frac{1}{2} & 0 \\ \frac{1}{2} & 0 & 0 & \frac{1}{2} \\ 0 & 0 & 0 & 1\end{bmatrix}$

EDIT the equation for mean first hitting time until set $R$ from state $1$ is

$$ m_{1, R} = p_{1,2} m_{2, R} + (1-p_{1,2})m_{1,R} $$ in your case you need 3 equations with 3 unknowns.

Solution 2:

Let the expected number of tosses until we get the pattern HTH be $a$.

Let the expected additional waiting time given that we have just tossed an H (and are not finished) be $b$.

Let the expected additional waiting time given that our last two tosses have been HT be $c$.

By conditioning, we have the following equations:

$$a=1+\frac{1}{2}b+\frac{1}{2}a;$$ This is because on our first toss, we have used up a toss. If we got an H, our expected additional time is $b$. If we got a T, we have made no progress, and our additional expected time is $a$.

$$b=1+\frac{1}{2}b+\frac{1}{2}c.$$

$$c=1+\frac{1}{2}a.$$

Since $a$, $b$, and $c$ are clearly finite, we can find them by solving the above system of three linear equations.

Solution 3:

I have seen a way to answer these types of problem here - https://www.codechef.com/wiki/tutorial-expectation

Using the technique described in the link, the answer can be found out as:

Let $x$ be the expected number of tosses required to get $HTH$, then we can find $x$ recursively:

1. If the first toss is $T$, then expected number of tosses now are $x+1$.

2. If the first toss is $H$, then two cases:

   1. If the second toss is $H$, then expected number of tosses now are $x$ (one is wasted in the first toss, but the second toss is still useful)
   2. If the second toss is $T$, then two cases:
      1. If the third toss is $H$, then the expected number is 3.
      2. If the third toss is $T$, then the expected number is $x+3$.

Adding all above mentioned cases:

$$x = \frac{1}{2}(x+1)+\frac{1}{2}(\frac{1}{2}(x)+ \frac{1}{2}(\frac{1}{2}(3)+\frac{1}{2}(x+3)))$$ Solving the above expression give $x=10$.

Solution 4:

Intuition? Dunno... Anyhow, consider $u$, $v$ and $w$ the mean number of draws necessary to produce H starting from nothing, HT starting from H, and HTH starting from HT, respectively. We are after the mean number of draws $t$ necessary to produce HTH, which is $t=u+v+w$.

Note that $u=2$ (first success when a success is H) and $v=2$ (first success when a success is T). If the first draw after HT is H, this draw produces HTH while if the first draw is T, one wasted one draw and one is back at the initial situation hence $t$ supplementary draws will be necessary. Thus, $w=\frac12\cdot1+\frac12\cdot(1+t)$.

This yields $t=u+v+w=4+w=4+1+\frac12\cdot t$, that is, $t=10$.

Exercise: Adapt the proof to uneven probabilities $p$ for H and $q=1-p$ for T, you should find $t=\dfrac1p+\dfrac1{p^2q}$.