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.

  • $\begingroup$ How do you know that $f^{-1}(y_n$ exists? Or isn't it a problem? $\endgroup$ – Marine Galantin Oct 20 at 15:07
  • $\begingroup$ 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 $\endgroup$ – user657324 Oct 20 at 15:30
  • $\begingroup$ Is not? What do you mean? $\endgroup$ – Marine Galantin Oct 20 at 15:35
  • $\begingroup$ 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 $\endgroup$ – user657324 Oct 20 at 17:26
  • $\begingroup$ 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 $\endgroup$ – user657324 Oct 20 at 17:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.