Given the following Data Processing Inequality $$X\rightarrow Y\rightarrow Z$$ one can say that $$I(X;Y) \geq I(X;Y|Z)$$ Intuition tells me this is not correct since conditioning reduces entropy and maybe increases mutual information.
Does anyone know how one can prove this? I am thinking entropy.
$$I(X;Y) =h(Y)-h(Y|X)$$$$I(X;Y|Z)= h(Y|Z)- h(Y|Z,X)$$
Does anyone know how to continue?
In general, there is no rule as to whether conditioning decreases or increases mutual information. $I(X;Y)$ can be less than, equal to, or greater than $I(X;Y|Z)$ depending on the joint distribution of $X,Y$ and $Z$.
In case of the Markov chain $X \to Y \to Z$, the latter is true: \begin{align*} I\left(X;Y|Z\right) &= H\left(X|Z\right) - H\left(X|Y,Z\right) \\ &= H\left(X|Z\right) - H\left(X|Y\right) \\ &\leq H\left(X\right) - H\left(X|Y\right) \\ &= I\left(X;Y\right) \end{align*} where the first and fourth lines are by the definition of mutual information, the third line is because conditioning reduces entropy, and the second line is because of the Markov chain: conditioned on $Y$; $X$ and $Z$ are independent.
In order to understand the intuition, think of the following example. Let $X$ represent whether the sky is cloudy, $Y$ represent whether it is raining, and $Z$ represent whether I get wet (The assumption in this example, of course, is that these random variables form a Markov chain: Me getting wet is independent of whether the sky is cloudy if I already know whether it is raining or not.).
Then, if you already knew that the sky is cloudy, then you could predict that it might rain, and thus you might get wet, hence the event that it is raining would provide you with less information, since it would tell you something you could already predict to some extent. If you do not know about the state of the sky, on the other hand, rain would be more of a surprise, hence more information.
Note: This would be the intuition for the inequality $I(Y;Z)\geq I(Y;Z|X)$, but it is essentially the same idea.