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\left( {n \ge 3} \right)\)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.

Short answer

The process is a Markov chain with stationary transition probabilities and the transition matrix is obtained.

Step-by-step solution

Verifying the process is a Markov chain with stationary transition probability

Consider an experiment of tossing a coin repeatedly, and occurrences of heads and tails are equally likely except for the following exception.

The fourth outcome is always the opposite whenever successive heads or tails are observed.

To prove that the process forms a Markov chain with stationary transition probabilities.

At any given time n, the state f the process is specified by the outcome on tosses at time\(\left( {n - 2} \right)\),\(\left( {n - 1} \right)\)and n.

Hence the states are:

\(s = \left\{ {\left( {TTT} \right),\left( {TTH} \right),\left( {THT} \right),\left( {HTT} \right),\left( {THH} \right),\left( {HTH} \right),\left( {HHT} \right),\left( {HHH} \right)} \right\}\)

Hence, there are 8 states.

Since the conditional probabilities of any triplet depends on the previous triplet, we can say that the process is a markov chain with stationary probabilities

Making the transition matrix

Consider the state triplet where not all outcomes are equal.

For example consider\(\left( {HTT} \right)\)the next state can be either\(\left( {THH} \right)\)or\(\left( {HTH} \right)\)

Each of these states will occurs with equal probability.

Let\(\left( {xyz} \right)\)be the three arbitrary elements of\(\left\{ {HTT} \right\}\)and are not equal.

Hence the row of\(\left( {xyz} \right)\)will contain 0 in every column except for two columns which have\(\left( {yzH} \right)\)or\(\left( {yzT} \right)\)and these columns have the probability 0.5.

Similarly the row\(\left( {TTT} \right)\)will have 0 in all the columns except column\(\left( {TTH} \right)\)which contain probability 1. The row\(\left( {HHH} \right)\)will have 0 in all the columns except column\(\left( {HHT} \right)\)which contain probability 1.

Hence the resulting transition matrix is as follows,

	HHH	HHT	HTH	HTT	THH	THT	TTH	TTT
HHH	0	1	0	0	0	0	0	0
HHT	0	0	0.5	0.5	0	0	0	0
HTH	0	0	0	0	0.5	0.5	0	0
HTT	0	0	0	0	0	0	0.5	0.5
THH	0.5	0.5	0	0	0	0	0	0
THT	0	0	0.5	0.5	0	0	0	0
TTH	0	0	0	0	0.5	0.5	0	0
TTT	0	0	0	0.5	0	0	1	0