# Confusion regarding the non-negativity of the relative entropy and how can $H(X|Y) \le H(X)$

Given the relative entropy is $$\ge 0$$:

If I take the relative entropy of $$p(x,y)$$ and $$p(x)$$, $$H(p(x,y)||p(x))=\sum_{x,y}p(x,y)log\frac{p(x,y)}{p(x)}$$, I keep getting $$H(X,Y) \le H(X)$$, which would mean the conditional entropy must be negative, which for shannon entropies cannot be the case. What am I doing wrong here?

• $p(x)$ is not a probability distribution on $\mathcal{X} \times \mathcal{Y}$. One way to see this is that $\sum_{x,y} p(x) = \sum_y \sum_x p(x) = \sum_y 1 = |\mathcal{Y}| > 1$ if $\mathcal{Y}$ is nontrivial. Aug 2, 2020 at 13:27
• @stochasticboy321 apologies for my confusion, I am not what your answer actually pertains to. $H(X|Y) =-\sum_{x,y}p(x,y)log\frac{p(x,y)}{p(x)}$, which is the condition entropy of $p(x,y$ and $p(x)$. Since it's the negative, I keep getting that it's $\le 0$. So are you saying my expansion is wrong or that it holds if $X$ is not on $X \times Y$ Aug 2, 2020 at 16:31
• Your answer is basically right. Non-negativity of relative entropy holds for probability distributions, not for general measures. If you were comparing two distributions $p,q$ on $\mathcal{X} \times \cal Y$ then you can say that $H(p\|q) \ge 0$. However, the measure $q$ you have is not a distribution on $\mathcal{X}\times \mathcal{Y}$, ergo you cannot assert that this is non-negative (in fact, since the expression you have is $-H(Y|X),$ it is negative). BTW, for the positivity of $H(Y|X)$, note that this is $\sum p(x,y) \log \frac{p(x)}{p(x,y)}$. Apply the log-sum inequality to this. Aug 2, 2020 at 17:20
• @stochasticboy321 thank you. Yeah I got the expression for $H(X|Y)$, but I didn't understand how to prove it. So $\sum_{xy}p(x,y)log\frac{p(y)}{p(x,y)} = -\sum_{xy}p(x,y)log\frac{p(x,y)}{p(y)}\ge \frac{1}{ln2}\sum_{xy}p(x,y)(1-\frac{p(x,y)}{p(y)})= \frac{1}{ln2}\sum_{xy}(p(x,y)-\frac{p(x,y)^2}{p(y)})=\frac{1}{ln2}\sum_{xy}p(x,y)-p(y)p(x|y)^2$ Given I am new to this I am unsure of where to go from here Aug 2, 2020 at 17:39
• Also btw the log-sum inequality trick I mentioned above is an oversimplification. The cleanest proof I know for $H(X|Y)\ge 0$ is that $H(X|Y) = \sum p(y) H(X|Y = y),$ where $H(X|Y = y)$ is the entropy of the law $p(x|y)$ (for a fixed $y$). Now each term in the sum is non-negative (because entropies are non-negative), so the whole sum is non-negative. Aug 2, 2020 at 18:14

Upon some research, the reason this is happening is because, as mentioned in the comments, the conditional entropy cannot be shown to be non-negative using the relative entropy. All you can do is find an expression for it in terms of $$-\sum_{x,y}p(x,y)log\frac{p(x,y)}{p(x)}$$, but there is no proof from this approach that it is $$\ge 0$$ Best explanations I have found are here