Confusion - Expected Waiting Times for pattern HHH

Question

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(HHH)=0$

$g(HHT)=g(THT)=0.5g(HTH)+0.5g(HTT)+1$

$g(HTH)=g(TTH)=0.5g(THH)+0.5g(THT)+1$

$g(HTT)=g(TTT)=0.5g(TTH)+0.5G(TTT)+1$

$g(THH)=0.5g(HHT)+1$

Then,

$g(HHT)=g(THT)=14$

$g(HTH)=g(TTH)=12$

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

Answer 1

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.

Answer 2

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

Answer 3

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