0
$\begingroup$

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?

$\endgroup$
8
  • $\begingroup$ $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. $\endgroup$ Aug 2, 2020 at 13:27
  • $\begingroup$ @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 $ $\endgroup$ Aug 2, 2020 at 16:31
  • $\begingroup$ 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. $\endgroup$ Aug 2, 2020 at 17:20
  • $\begingroup$ @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 $\endgroup$ Aug 2, 2020 at 17:39
  • 1
    $\begingroup$ 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. $\endgroup$ Aug 2, 2020 at 18:14

1 Answer 1

1
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .