9
$\begingroup$

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.

$\endgroup$
1

2 Answers 2

13
$\begingroup$

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.

$\endgroup$
10
  • $\begingroup$ How do you know that $f^{-1}(y_n$ exists? Or isn't it a problem? $\endgroup$ Commented Oct 20, 2019 at 15:07
  • 1
    $\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
    Commented Oct 20, 2019 at 15:30
  • $\begingroup$ Is not? What do you mean? $\endgroup$ Commented Oct 20, 2019 at 15:35
  • 1
    $\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
    Commented Oct 20, 2019 at 17:26
  • 1
    $\begingroup$ To be clear, in this context $f^{-1}$ refers to the inverse, not the pre-image. If $f$ is injective, its inverse $f^{-1}:\mathcal Z \to \mathcal X$ is well-defined, where $\mathcal Z$ is the image of $f$. It is obvious that the $Y_n=f(X_n)\in\mathcal Z$, so there is no need to consider $Y_n=y_n$ for $y_n\notin\mathcal Z$. $\endgroup$
    – Jason
    Commented Oct 25, 2019 at 0:28
0
$\begingroup$

Not necessarily, for a general criteria see "Markov property for a function of a Markov chain: A linear algebra approach"

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .