# Proving $X$, $Y$, $g(Y)$ is a Markov Chain in That Order

I wondering how to prove $X$, $Y$, $g(Y)$ is a Markov Chain in That Order?

$X$, $Y$, $Z$ is a Markov Chain in That Order (denoted $X\to Y\to Z$) if $$p(x,y,z) = p(x)\cdot p(y\mid x)\cdot p(z\mid y).$$ A property of a Markov Chain is if $X\to Y\to Z$, then $$p(xz\mid y) = p(x\mid y)\cdot p(z\mid y).$$

Setting $Z = g(Y)$, I must show: $p(x,y,g(y)) = p(x)\cdot p(y\mid x)\cdot p(g(y)\mid y)$.

I believe I must simplify $p(g(y)\mid y)$ somehow, but I am only aware of conditional expectation identity where $E[g(Y)\mid Y] = g(Y)$ and $E[g(Y)\mid Y=y] = g(y)$.

-

We know that for any $X,Y,Z$:

$$p(X,Y,Z) = p(X) \cdot p(Y|X) \cdot p(Z|X,Y)$$

And it is a Markov Chain if:

$$p(Z|X,Y) = p(Z|Y)$$

Therefore, to show that $X,Y,g(Y)$ is a Markov Chain, we must show that:

$$p(g(Y)|X,Y) = p(g(Y)|Y)$$

This is trivial, because:

$$p(g(Y)=z|X=x,Y=y) = \begin{cases} 1 &\text{if } z = g(y), \\ 0 &\text{if } z \ne g(y) \end{cases}$$

That is, $g(Y)$ is uniquely determined by $Y$, which is to say, $X$ and $g(Y)$ and conditionally independent.

-

We wish to prove if $Z = f(Y)$, then $X\to Y\to Z$.

We want to show: $p(x,y,z) = p(x)p(y\mid x)p(z\mid y)$, where $z=g(y)$. The following statement is always true:

$p(x,y,z) = p(x)p(y\mid x)p(z\mid yx)$. To reach the desired statement, we only need to show: $p(z \mid yx) = p(z \mid y)$.

$$p(z \mid yx) = \begin{cases} 1, & z = g(y) \\ 0, & z \neq g(y)\end{cases}$$

Notice that $p(z \mid yx)$ does not depend on $x$. Then, $p(z \mid yx) = p(z \mid y)$ and we have proved $X \to Y \to Z$, when $Z = g(Y)$.

-
Additional resource could be found here: cims.nyu.edu/~chou/notes/infotheory.pdf – jrand Nov 8 '12 at 22:33