Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
Actually the opposite inequality is only true. "Conditioning increases divergence". Search with these words, you will get several references. –  Ashok May 24 '12 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 '12 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 '12 at 6:19
Yes, that is true. –  Vladimir May 25 '12 at 11:25

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.