2
$\begingroup$

I am looking at relative entropy=KL-divergence and trying to prove, at least in case of probability mass functions $q,\,p$ with possible states $x\in A$ that if:

$$ D(p \,\lVert\,q)=\sum_{x\in A}p\left(x\right)\,\log\left[\frac{p\left(x\right)}{q\left(x\right)}\right] = 0 $$

then $p\left(x\right)=q\left(x\right)\: \forall x \in A$.

I can see that the converse is true, and my book Cover, Thomas Elements of Information Theory does state that the above result is also valid, but the proof there is, in my opinion, incomplete. The authors use concavity of $\log$ to prove that $D(p \,\lVert\,q)>0$ (happy there). And then state, that the only way to have equality, as opposed to inequality, is to have $,\log\left[\frac{p\left(x\right)}{q\left(x\right)}\right]$ being not strictly concave. Sort of ok with that (not too happy), but then the authors state that the only way to get that is to have $\left[\frac{p\left(x\right)}{q\left(x\right)}\right]=const$. I am not sure how to make that last jump.

Can anyone help? Or suggest an alternative proof? Thanks

$\endgroup$
1
$\begingroup$

"The only way to have equality is to have $\log \frac{p(x)}{q(x)}$ being not strictly concave" is a weird way to say something here, so you may have misread the proof, or it may be badly worded. However, the idea is to figure out the equality case of the inequality we used to prove that KL-divergence is nonnegative.

To begin with, here's a proof that KL-divergence is nonnegative, which is probably essentially the same as the one you read. Let $f(x) = -\log x = \log \frac1x$; this is a strictly convex function on the positive reals. Then by Jensen's inequality $$ D(p\,\|\,q) = \sum_{x \in A} p(x) f\left(\frac{q(x)}{p(x)}\right) \ge f\left(\sum_{x \in A} p(x) \frac{q(x)}{p(x)}\right) = f(1) = 0. $$ For a strictly convex function like $f(x)$, assuming that the weights $p(x)$ are all positive, equality holds if and only if the inputs to $f$ are all equal, which directly implies $\frac{q(x)}{p(x)}$ is constant and therefore $p(x)=q(x)$ for all $x$.

We have to be careful if $p(x)=0$ for some inputs $x$. Such values of $x$ are defined to contribute nothing to the KL-divergence, so essentially we have a sum over a different set $A' = \{x \in A : p(x) > 0\}$. Then on the right-hand side of the inequality, we get $$ f\left(\sum_{x \in A'} p(x) \frac{q(x)}{p(x)}\right) = f\left(\sum_{x \in A'} q(x)\right). $$ But now, if the sum over $A'$ is some probability $q<1$, then $f(q) > 0$, and we conclude $D(p\,\|\,q) > 0$. So the sum of $q(x)$ over $A'$ should be $1$. We conclude that when the KL-divergence is $0$, $p(x)=0 \implies q(x)=0$ for all $x \in A$. In order for the KL-divergence to even be defined, $q(x)=0 \implies p(x)=0$ for all $x\in A$. So we can throw away any values where $p(x)=q(x)=0$, and now we're back in the simple case, where all the weights in Jensen's inequality are positive.

$\endgroup$
2
  • 1
    $\begingroup$ Thanks! I think I can fix this in my head by saying that strict convexity means $$\lambda f\left(x_1\right)+\left(1-\lambda\right)f\left(x_2\right)>f\left(\lambda x_1+(1-\lambda) x_2\right),\: \forall x_1\neq x_2,\,\lambda\in \left(0,\,1\right) $$ Therefore equality for a strictly convex function implies that one of the conditions is violated, and since the probabilities are not zero or one, the $x_{\dots}$ s must be equal $\endgroup$
    – Cryo
    Nov 15 '20 at 18:01
  • 1
    $\begingroup$ Yes, that's a good way to think about it. $\endgroup$ Nov 15 '20 at 18:07

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.