# Markov chain and mutual information equality

Consider a distribution $$P(X,Y,Z)$$ and a Markov chain $$Z-Z'$$. Does the following equality hold in general? $$I(X;Y \mid Z) = I(X;Y \mid Z,Z')$$

• What's a Markov chain $Z-Z'$? Do you mean that $Z'$ is the next state in the chain and $Z$ is the previous state? – Aleksejs Fomins Jan 18 at 10:15
• I mean that $Z'$ is derived from $Z$ through a (deterministic or random) function. – Cesare Jan 18 at 10:17
• Ok this makes sense – Aleksejs Fomins Jan 18 at 10:18

Yes, it does hold in general. You can't create new information by performing deterministic or random operations on a variable, only destroy information or keep information the same. So all of the info in $$Z'$$ is already contained in $$Z$$. See wiki for proof for entropies. Proof for conditional mutual information follows analogously.

Edit: Ok, here's a formal derivation. Firstly, let's formalize the Markov Chain by saying that $$Z' = f(Z, G)$$, where $$f$$ is some deterministic function, and $$G$$ is some random variable (possibly vector-valued), which is completely unrelated to $$Z$$ and which denotes the random part of the step function. Now let's try to find the joint entropy $$H(Z, Z')$$

$$H(Z, Z') = H(Z) + H(Z' | Z) = H(Z) + K_1$$

This is a sum of two numbers. The first number only depends on the probability distribution of $$Z$$. The second number (which I will call K_1) explicitly does not depend on the distribution of $$Z$$, because we have conditioned it out. Hence, it will only depend on $$G$$. How exactly it depends on $$G$$ turns out to be irrelevant. We can also extend this result by assuming there is one or more extra variables in the expression

$$H(X, Y, Z, Z') = H(X, Y, Z) + H(Z' | X, Y, Z) = H(X, Y, Z) + K_2$$

Next, we will transform the original expression and try to apply this result

$$I(X;Y| Z, Z') = H(X,Y,Z,Z') - H(Z,Z') = H(X, Y, Z) + K_2 - H(Z) - K_1 = I(X; Y | Z) + K_2 - K_1$$

So what remains to be proven is that $$K_1 = K_2$$, or, explicitly

$$H(Z'|Z) = H(Z'|X,Y,Z)$$

Again, this last one seems completely obvious logically, namely, that conditioning using variables that do not deliver extra information compared to what is already conditioned upon does not change anything. I can't immediately recall how to prove this last one. I'll look it up when I get the chance

• Do you have a formal derivation? – Cesare Jan 18 at 11:36