1

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.

flag
Actually the opposite inequality is only true. "Conditioning increases divergence". Search with these words, you will get several references. – Ashok May 24 2012 at 10:53
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. – Vladimir May 25 at 1:30
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)$. – Ashok May 25 at 6:19
Yes, that is true. – Vladimir May 25 at 11:25

Your Answer

Get an OpenID
or

Browse other questions tagged or ask your own question.