Let
{Xn} be a Markov chain with transition probability matrix P and state-space {0, 1, 2, . . . , M }.

For each of the following, show that
{Yn} is a Markov chain (in which case you exhibit the
transition matrix) or give a counter-example showing that
{Xn} is NOT a Markov chain:

1. Yn= g(Xn ), where g(x) is an arbitrary function.
2. Yn = (Xn−1 , Xn), n= 1, 2, . . .. That is, the state-space of {Yn} is formed by pairs of numbers {(0, 0), (0, 1), . . . , (M,M )}.