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.

  • $\begingroup$ I see -- I'll delete my comment then, but this definitely has a feeling of "data processing inequality." $\endgroup$ – Clement C. Mar 6 '16 at 16:51
  • 1
    $\begingroup$ 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))$. $\endgroup$ – 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}

  • $\begingroup$ 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. $\endgroup$ – Mikhail Goltvanitsa Mar 6 '16 at 19:19
  • $\begingroup$ 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? $\endgroup$ – Boby Mar 7 '16 at 0:08
  • $\begingroup$ I am using the following book: Checheta S.I. Introduction to discrete information and coding theory (in Russian). $\endgroup$ – Mikhail Goltvanitsa Mar 7 '16 at 6:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.