1. Let fXng be a stationary Markov chain with transition matrix P and g a one-to-one function. DefineYn D g.Xn/. Prove that fYng is a Markov chain, and characterize as well as you can the transition probability matrix of fYng.

2. * (Loop Chains). Suppose fXng is a stationary Markov chain with state space S and transition probability matrix P .

(a) Let Yn D .Xn; XnC1/. Show that Yn is also a stationary Markov chain.

(b) Find the transition probability matrix of Yn.

(c) How about Yn D .Xn; XnC1; XnC2/? Is this also a stationary Markov chain?

(d) How about Yn D .Xn; XnC1;::: ; XnCd / for a general d > 1?

3. (Dice Experiments). Consider the experiment of rolling a fair die repeatedly. Define

(a) Xn D the number of sixes obtained up to the nth roll;

(b) Xn D the number of rolls, at time n, that a six has not been obtained since the last six.

Prove or disprove that each fXng is a Markov chain, and if they are, obtain the transition probability matrices.