1
$\begingroup$

Let $p$ and $q$ be two joint distributions of finite random variables $X$ and $Y$. Recall the definition of conditional KL divergence between $p$ and $q$ of $X$ conditioned on $Y$: $D_{KL}(q(X|Y)||p(X|Y)) = \sum_yq(y)D_{KL}(q(X|Y=y)||p(X|Y=y))|Y=y]$ (e.g., Cover and Thomas, Elements of Information Theory).

Is it true that $D_{KL}(q(X|Y)||p(X|Y)) \leq D_{KL}(q(X)||p(X))$, in analogy to the inequality for entropy $H(X|Y) \leq H(X)$ ?

Note: it may seem like the opposite inequality follows from the convexity of KL divergence, but this is clearly not the case.

Improve this question
$\endgroup$
4
  • $\begingroup$ Actually the opposite inequality is only true. "Conditioning increases divergence". Search with these words, you will get several references. $\endgroup$
    – Ashok
    May 24, 2012 at 10:53
  • $\begingroup$ It is true that in some sense "conditioning increases divergence", but it is not true (as I note in the question) that the opposite inequality is true. For example, if you condition $X$ on $X$ then the l.h.s. is zero, while the r.h.s. is generally not. $\endgroup$
    – Vladimir
    May 25, 2012 at 1:30
  • $\begingroup$ Yes, you are right. But I don't know how to interpret your result. The sense in which "Conditioning increases divergence" is the following. Suppose that $X,\hat{X}$ are two r.v's on the alphabet $A$ and $Y$ is a r.v. on $B$. Let $p(x,y), q(\hat{x},y)$ be the joint pmf's of $(X,Y)$ and $(\hat{X},Y)$ repectively (i.e. $p$ and $q$ have same $y$-marginal). Then the side information ($Y$) increases the divergence, i.e., $D(q(\hat{X}|Y)\|p(X|Y)) \geq D(q_{\hat{X}}\|p_X)$. $\endgroup$
    – Ashok
    May 25, 2012 at 6:19
  • $\begingroup$ Yes, that is true. $\endgroup$
    – Vladimir
    May 25, 2012 at 11:25

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.