MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|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.