So the problem is: Let $THT$ be the (random) number of times we need to flip a coin before we have gotten a Heads followed by a Tails. Consider Markov chain with transition probability with state space {$HHH,HHT,HTH,HTT,THH,THT,TTH,TTT$}:

$$ \begin{bmatrix}0.5 &0.5&0&0&0&0&0&0 \\0 & 0&0.5&0.5&0&0&0&0\\0&0&0&0&0.5&0.5&0&0\\0&0&0&0&0&0&0.5&0.5\\0.5 &0.5&0&0&0&0&0&0 \\0 & 0&0.5&0.5&0&0&0&0\\0&0&0&0&0.5&0.5&0&0\\0&0&0&0&0&0&0.5&0.5\end{bmatrix}$$

what is the expected waiting time for $HHH$?

The answer says:

Let $g(XXX)$ be the average time for the Markov chain to go from state $XXX$ to state $HHH$, where $X$ can be either $T$. Then,









$ g(HTT)=g(TTT)=14 $

$ g(THH)=8 $

So the average number of tosses to get $HHH$ is $3+0.125(0+8+4*14+2*12)=14$

My question is :Where do the equations come from? For example, why is $0.5g(HTH)+0.5g(HTT)+1$ the avearge time for $HHT$ to return to $HHH$?

  • $\begingroup$ This is hard to follow. how can $THT$ be the number of times of anything? It's a binary string, not a number. $\endgroup$ – lulu Oct 13 '16 at 11:53

It is assumed that, for long runs of random walks, the average time of going from one state to another state is a fixed number. Now, we just want to make a system of equations to find them. For the example, that you have given, if you want to go from $HHT$ to $HHH$, you have to go to either $HTH$ or $HTT$, in the first step. With probability $0.5$, you go to $HTH$ and you know the expected time to get to $HHH$, from it. The same is true for the second possibility (to $HTT$). So, you just average them and add a $1$ to them, just because you have considered that you have taken one step to go from $HHT$ to the two adjacent states.


To phrase the calculation differently, we consider states defined by the last toss (or the last two tosses). Specifically we consider the state $S_n$ where we the past tosses are a string of exactly $n$ $H's$. Thus if you have tossed $THHTHT$, reading from left to right, you have wound up back in $S_0$ since the last toss was a $T$. Similarly, the sequence $HTTTHTHH$ winds up in $S_2$. We want to know the expected number of tosses it takes to get to $S_3$. Let $E_n$ be the expected number of tosses it takes to reach $S_3$ given that you are in $S_n$, so the answer we want is $E_0$.

Starting in $S_0$ we remark that the next toss either leaves you in $S_0$ or takes you to $S_1$. Thus $$E_0=\frac 12\times \left(E_0+1\right)+\frac 12\times \left(E_1+1\right)$$ It follows that $$E_1=E_0-2$$ Similarly, $$E_1=\frac 12\times \left(E_0+1\right)+\frac 12\times \left(E_2+1\right)\implies E_2=E_0-6$$ And $$E_2=\frac 12\times \left(E_0+1\right)+\frac 12\times \left(E_3+1\right)\implies E_3=E_0-14$$ But $E_3=0$, clearly, whence $E_0=\fbox {14}$


For example, why is $0.5~g(HTH)+0.5~g(HTT)+1$ the average time for $HHT$ to return to $HHH$ ?

Starting at $\sf \bbox[1pt]H\bbox[lemonchiffon,1pt]H\bbox[lemonchiffon,1pt]T$, after the next toss you will either be in state $\sf\bbox[lemonchiffon,1pt]H\bbox[lemonchiffon,1pt]T\bbox[1pt]H$ or $\sf\bbox[lemonchiffon,1pt]H\bbox[lemonchiffon,1pt]T\bbox[1pt]T$ with equal probability.

Thus the expected time to move from $\sf HHT$ to $\sf HHH$ is that one step plus the expected time to reach $\sf HHH$ from the next state, whichever it may be.   Use the Law of Total Expectation. $$g(\mathsf{HHT})~=~ 1+\tfrac 12g(\mathsf{HTH})+\tfrac 12g(\mathsf{HTT})$$


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.