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')
$$
 A: 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
