This question is from DEGROOT's "Probability and Statistics".
Question:
Suppose that a coin is tossed repeatedly in such a way
that heads and tails are equally likely to appear on any
given toss and that all tosses are independent, with the
following exception: Whenever either three heads or three
tails have been obtained on three successive tosses, then
the outcome of the next toss is always of the opposite type.
At time $n (n ≥ 3)$, let the state of this process be specified
by the outcomes on tosses $n − 2$, $n − 1$, and $n$. Show that
this process is a Markov chain with stationary transition
probabilities and construct the transition matrix.
The answer at the back of the book :
$$\begin{array}{c|lcr}
& \text{HHH} & \text{HHT} & \text{HTH} & \text{THH} & \text{TTH} & \text{THT} & \text{HTT} & \text{TTT} \\
\hline
HHH & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\
HHT & 0 & 0 & \frac{1}{2} & 0 & 0 & 0 & \frac{1}{2} & 0 \\
HHH & 0 & 0 & 0 & \frac{1}{2} & 0 & \frac{1}{2} & 0 & 0 \\
THH & \frac{1}{2} & \frac{1}{2} & 0 & 0 & 0 & 0 & 0 & 0 \\
TTH & 0 & 0 & 0 & \frac{1}{2} & 0 & \frac{1}{2} & 0 & 0 \\
THT & 0 & 0 & \frac{1}{2} & 0 & 0 & 0 & \frac{1}{2} & 0 \\
HTT & 0 & 0 & 0 & 0 & \frac{1}{2} & 0 & 0 & \frac{1}{2} \\
TTT & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\
\end{array}$$
But I don't know how to show that this process is a Markov chain.
Actually, I can't understand the meaning of the sentence: At time $n (n ≥ 3)$, let the state of this process be specified
by the outcomes on tosses $n − 2$, $n − 1$, and $n$.
Please help me showing this a Markov chain. Thank you.
Best Answer
Say you've tossed the coin ten times and the result is $$ HHTHTTTHTH $$ Then view it like this: $$ HHTHTTT\,\overbrace{HTH} $$
At that point the state of the Markov chain is $HTH$, i.e. the state is given by the last three tosses. If you then get $T$ on the next toss, then the whole history is $$ HHTHTTT\,\overbrace{HTH}\,T $$ and you look at the last three tosses: $$ HHTHTTTH\,\overbrace{THT} $$ and the state becomes $THT$. If you get $H$ instead, then the state becomes $THH$. You have probability $1/2$ of either of those outcomes.
In other words, if you've toss the coin $11$ times, so that $n=11$, then $n-1=10$ and $n-2=9$, and the state of the system is determined by the $9$th, $10$th, and $11$th tosses.
Thus from the state $HTH$ one can transition into either of the two states $THH$ or $THT$ with equal probabilities. But if the state is $TTT$ then one necessarily (thus with probability $1$) goes next to the state $TTH$, and if the state is $HHH$ then the next state is necessarily $HHT$.