What is the expected value of getting the string THT?

Question

I've gotten up to the point where I have the number of expected flips needed to get the string TH, but it is after that I am running into trouble.

Expected Value to get String 'T':

E(T) = E(T|T on the first toss)*P(T on the first toss) + E(T|H on the first toss)*P(H on the first toss)

E(T) = 1*1/2 + (E(T))*1/2 E(T) = 2

Expected Value to get String 'TH', given T on first toss:

E(TH) = E(TH|H on the second toss)*P(H on the second toss) + E(TH|T on the second toss)*P(T on the second toss)

E(TH) = 1*1/2 + ((E(TH)) + 1)*1/2 E(TH) = 2

Expected Value to get String 'THT', given T on first toss, H on second toss:

E(THT) = E(THT|T on third toss)*P(T on third toss) + E(THT|H on third toss)*P(H on third toss)

Here is where I have trouble.

I know this much:

E(THT) = 1*1/2 + E(THT|H on third toss) * 1/2

But I initially thought that E(THT|H on third toss) would be 3 + E(T) + E(TH) + E(THT), however this leads me to a total summed up expected value of 12, which I know is wrong.

What am I doing wrong?

EDIT: E(TH) represents the expected number of tosses needed to get TH starting at the beginning.

Answer 1

I have tried editing and that doesn't seem to work and I can't comment, but E(TH) represents the expected value to get the string TH when starting at the beginning.

EDIT: I apologize I messed up my explanation of my notation. E(T)represents the number of expected tosses to get to The from the beginning. E(TH) represents the number of tosses to get to TH from T. Then E(THT) represents the number of tosses to get from TH to THT

Answer 2

Construct an absorbing markov chain, then use it's fundamental matrix, $(\mathbf I-\mathbf Q)^{-1}$. $$\begin{align} & \begin{array}{c|cccc} P & \{\} & \{T\} & \{TH\} & \{THT\} \\ \hline \{\} & \tfrac 1 2 & \tfrac 1 2 & 0 & 0 \\ \{T\} & 0 & \tfrac 1 2 & \tfrac 1 2 & 0 \\ \{TH\} & \tfrac 1 2 & 0 & 0 & \tfrac 1 2 \\ \{THT\} & 0 & 0 & 0 & 1 \end{array} \\ (\mathbf I_3-\mathbf Q)^{-1}\mathbf 1_3 & = \left(\begin{bmatrix}1&0&0\\0&1&0\\0&0&1\end{bmatrix}-\begin{bmatrix}\tfrac 12 & \tfrac 12 & 0\\0&\tfrac 12 & \tfrac 1 2\\ \tfrac 12 & 0 & 0\end{bmatrix}\right)^{-1}\times\begin{bmatrix} 1 \\ 1 \\ 1\end{bmatrix} \\ & = \begin{bmatrix}\tfrac 12 & -\tfrac 12 & 0\\ 0 & \tfrac 12 & -\tfrac 1 2\\ -\tfrac 12 & 0 & 1\end{bmatrix}^{-1}\times\begin{bmatrix} 1 \\ 1 \\ 1\end{bmatrix} \\ & = \begin{bmatrix}2 & 2 & 1\\ 1 & 2 & 1\\ 1 & 1 & 1\end{bmatrix}\times\begin{bmatrix} 1 \\ 1 \\ 1\end{bmatrix} \\ & = \begin{bmatrix}10 \\ 8 \\ 6\end{bmatrix} \end{align}$$

The expected steps to absorption when starting from position $i$ is the $i$ row entry of this matrix. That is: the expected time to reaching the end of the target sequence is 10 flips.

Answer 3

Define the following random variables:

$X_1$ is the number of flips needed to obtain your first $T$.

$X_2$ is the number of additional flips, after the first $T$, to obtain a $THT$ which may or may not include the $T$ that we're starting from.

Then you are asking for $E(X)$, where $X = X_1 + X_2$. Thus $E(X) = E(X_1) + E(X_2)$.

It is not hard to show that $E(X_1) = 2$. To calculate $E(X_2)$, assume that we've just obtained a $T$. Then:

(1) If the next flip is a $T$, then it will take, on average, an additional $E(X_2)$ flips. (We've started over at the same stage of just having had a $T$.)

(2) If the next two flips are $HH$, then it will take, on average, an additional $E(X)$ flips. (It's as if we've started over from the beginning.)

(3) If the next two flips are $HT$, then we're done.

So we obtain the equation $$E(X_2) = (1/2)[1 + E(X_2)] + (1/4)[2 + E(X)] + (1/4)2.$$ Combining this with $E(X) = 2 + E(X_2)$, we obtain $E(X) = 10$.