A function of a Markov chain is necessarily again a Markov chain? I was curious about the above questions. If the answer is not, is there a mathematical proof of that?
e.g. given a function $f:\mathcal X \rightarrow \mathcal Y$, with $\mathcal X$ a finite state space, find a Markov Chain $(X_n)_{n\ge 0}$ such that $(Y_n)_{n\ge 0}$ with $Y_n = f(X_n)$ is not a Markov Chain.
 A: This depends on $f$. In fact, $Y_n=f(X_n)$ is a Markov chain in $\mathcal Y$ for every Markov chain $(X_n)$ in $\mathcal X$ if and only if $f$ is either injective or constant. If $f$ is constant then $(Y_n)$ is trivially a Markov chain. If $f$ is injective, then
$$P(Y_{n+1}=y_{n+1}|Y_k=y_k\text{ for }k\le n)=P(X_{n+1}=f^{-1}(y_{n+1})|X_k=f^{-1}(y_k)\text{ for }k\le n)\\
=P(X_{n+1}=f^{-1}(y_{n+1})|X_n=f^{-1}(y_n))=P(Y_{n+1}=y_{n+1}|Y_n=y_n).$$
However, if $f$ is neither injective nor constant, there exists $y,z\in\mathcal Y$ and $x_1,x_2,x_3\in\mathcal X$ (with $x_1\neq x_2$) such that $f(x_1)=f(x_2)=y\neq z=f(x_3)$. Define a transition kernel on $\mathcal X$ by $p(x_1,x_3)=p(x_3=x_1)=1$, $p(x,x)=1$ otherwise. In other words the chain stays where it is with probability one unless it is at $x_1$ or $x_3$, in which case it switches.
Assuming $X_0$ is uniformly distributed on $\{x_1,x_2,x_3\}$, we have
$$P(Y_2=z|Y_1=y)=\frac{P(Y_2=z,Y_1=y)}{P(Y_1=y)}=\frac{P(X_0=x_3)}{P(X_0\in\{x_1,x_3\})}=\frac12.$$
Let's break down the steps. The first step is just definition of conditional probability. The second comes from noting that $Y_1=y,Y_2=z$ if and only if $X_1=x_1,X_2=x_3$ (otherwise the chain cannot move) which happens if and only if $X_0=x_3$, and similarly $Y_1=y$ if and only if either $X_0=x_1$ or $X_0=x_3$. The third step comes from the fact that $X_0$ is uniform over $\{x_1,x_2,x_3\}$.
On the other hand, we have
$$P(Y_2=z|Y_0=z,Y_1=y)=\frac{P(Y_0=z,Y_1=y,Y_2=z)}{P(Y_0=z,Y_1=y)}=\frac{P(X_0=x_3)}{P(X_0=x_3)}=1$$
using similar steps. These are not equal, so $(Y_n)$ is not a Markov chain.
A: Not necessarily, for a general criteria see
"Markov property for a function of a Markov chain: A linear algebra approach"
