0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Can you say in words what your notation E(TH) means? $\endgroup$ – Dave Sep 11 '14 at 23:10
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ The Markov chain approach is standard but the inversion of the matrix is not fully necessary. $\endgroup$ – Did Sep 12 '14 at 6:19
2
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Don't close your browser. You need to keep the cookies the site has set. You mean the expected number of flips to obtain TH starting from the beginning, right? You seem to be saying that this is 2. That's wrong. Have a look at my answer here for some ideas. math.stackexchange.com/questions/923173/… $\endgroup$ – Dave Sep 11 '14 at 23:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.