# 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.

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.
• How do you know that $f^{-1}(y_n$ exists? Or isn't it a problem? – Marine Galantin Oct 20 at 15:07
• If $f$ is not injective, $$P(f(X)=k)=P(X\in f^{-1}(k)).$$ So at the end, you can consider these equality as inclusion (I think) @MarineGalantin – user657324 Oct 20 at 15:30
• What "is not" ? $\mathbb P(f(X)=k)=\mathbb P(X\in f^{-1}(k))$ ? Of course it is ! Simply because $$f(X)=k\iff X\in f^{-1}(k).$$ @MarineGalantin – user657324 Oct 20 at 17:26
• But at the end, in this answer, the OP precise that $f$ is injective so it's really an equality : "If 𝑓 is injective, then...". Maybe in the futur you should read more carefully answers before asking question ;) @MarineGalantin – user657324 Oct 20 at 17:38