Entropy Inequality $H(X| g(Y))\geq H(X|Y)$

Let $X,Y$ be random discrete variables. $H(X) = -\sum\limits_{x}P\{X=x\}\operatorname{log}_2P\{X=x\}$ be the entropy-function. It is known fact that that $H(g(Y))\leq H(Y)$. I want to prove the following inequality, which seems to be obvious in terms of common-sense: $$H(X|g(Y))\geq H(X|Y).$$ But formall proof is sufficiently bulky. Maybe somebody know an elegant proof of this fact.

• I see -- I'll delete my comment then, but this definitely has a feeling of "data processing inequality." – Clement C. Mar 6 '16 at 16:51
• I think so,too. But it is not straightforward consequence of the fact that $H(g(Y))\leq H(Y)$ and $H(X|g(Y)) = H(X,g(Y))- H(g(Y))$. – Mikhail Goltvanitsa Mar 6 '16 at 16:53

Use data processing inequality since $X \to Y \to g(Y)$ \begin{align} I(X;Y) &\ge I(X;g(Y)) \\ H(X)-H(X|Y) &\ge H(X)-H(X|g(Y)), \text{ chain rule }\\ H(X|Y) &\le H(X|g(Y)) \end{align}
• Thank you very much! I thought that "data processing inequality" is the inequality of the form $H(g(Y))\leq H(Y)$. (In my book it is in this form). In my first raw solution i have used only this simple inequality and have proved log sum inequality to solve the problem. – Mikhail Goltvanitsa Mar 6 '16 at 19:19
• You welcome. The inequality $H(Y) \le H(g(Y))$ can be considered a special instance form of data processing inequality. However, the inequality that involves mutual information is what one usually thinks of when people say data processing. What book are you using? – Boby Mar 7 '16 at 0:08