Show that a function of a markov chain is not a markov chain

Question

How do you show that a function, $Y(n)=g(X(n))$ if some Markov chain $X(n)$ cannot be a Markov chain?

Answer 1

Some functions of Markov chains are Markov chains. For example, if you're working on a finite state space and $Y$ simply is a permutation of the states, then the result is still a Markov chain.

In general, a function of a Markov chain as described forms a Hidden Markov Model. To see if the function is not a Markov chain, simply check the Markov property: Does $P(Y(n)=y_n | Y(n-1)=y_{n-1}, Y(n-2)=y_{n-2}, \ldots) = P(Y(n)=y_n | Y(n-1)=y_{n-1})$? If so, it is a Markov chain. If not, it is not a Markov chain.