2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Thanks a lot. Your explanation is amazing!! $\endgroup$
    – Silent
    Oct 7 '13 at 3:33

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.