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

Question

Can someone please explain why is the expected number of coin tosses to get the sequence of $HTH$ is $10$? What is the intuition and formulas behind this?

Answer 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.

Answer 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.

Answer 3

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

Answer 4

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

Answer 5

Intuitively I feel it makes sense because the probability of getting HTH (or any specific combination) is 1/8.

For one combination of HTH to be included in your series of coin flips, you would have an expected value of 8 sets of three-coin tosses each. ie. 10 total flips. (if the flips were numbered 1-10, the sets of three would be 123;234; ... ;789;8910)

Therefore you will have 8 sets of three-coin flips, and with a 1/8th probability of success your expected number of such combinations is 1.