Let P and Q be transition probability matrices on states 1, . . . , m, with respective transition probabilities Pi,j and Qi,j . Consider processes {Xn,n ≥ 0} and

{Yn,n ≥ 0} defined as follows:

(a) X0 = 1. A coin that comes up heads with probability p is then flipped.

If the coin lands heads, the subsequent states X1,X2, . . ., are obtained by using the transition probability matrix P; if it lands tails, the subsequent states X1,X2, . . . , are obtained by using the transition probability matrix Q. (In other words, if the coin lands heads (tails) then the sequence of states is a Markov chain with transition probability matrix P (Q).) Is

{Xn,n ≥ 0} a Markov chain. If it is, give its transition probabilities. If it is not, tell why not.

(b) Y0 = 1. If the current state is i, then the next state is determined by first flipping a coin that comes up heads with probability p. If the coin lands heads then the next state is j with probability Pi,j ; if it lands tails then the next state is j with probability Qi,j . Is {Yn,n ≥ 0} a Markov chain. If it is, give its transition probabilities. If it is not, tell why not.