I am considering the following question:
A fair coin is repeatedly and independently tossed until the pattern $HTH$ appears.
What is the probability that the game ends exactly at the $6$th flip?
I tried it using two approaches.
In first approach, I said that I can get any pattern on first three tosses except $HTH$ and then from $4$th to $6$th tosses, I should get pattern $HTH$.
So the required probability should be $(7/8)*(1/8)=7/64$.
In second approach, I took Markov chain route. I defined 4 states.
State $1$: We are nowhere in the pattern.
State$2$: we are one character$(H)$ into the pattern
State$3$:We are $2$ characters $(HT)$into the pattern
State $4$: Desired pattern $HTH$.
This is an absorbing state.
The transition probability matrix is :
$\begin{bmatrix}0.5 & 0.5 & 0 & 0\\0 & 0.5 & 0.5 & 0\\0.5 & 0 & 0 & 0.5\\0 & 0 & 0 & 1\end{bmatrix}$
By finding the $5$-step distribution vector, I was able to find the probability of pattern being in state $3$ after $5$ flips as $0.150625$ or $5/32$ as the pattern must be in state $3$ after the $5$th flip of the coin so as to be able to get pattern $HTH$ on $6$th flip which happens with a probability of $1/2$.
Hence using this approach the required probability comes out to be $(5/32)*(1/2)=5/64$ which is different from the probability I got using first approach.
I do not understand why is this happening. Why do the two approaches yield different results?
Which one is correct approach or are both faulty? Please help me out here.
Best Answer
If the first three tosses are $HHT$ or $THT$, the fourth toss of $H$ will terminate the sequence early. Thus the first approach overcounts.