2

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.

Silent
  • 6,520

1 Answers1

1

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

Michael Hardy
  • 1