Is there an inequality to relate the KL divergence of two joint distribution and the sum of the KL divergence of their marginals? Or in particular, is there a proof or a counter example for the following:

$D(q(x,y)\|p(x,y)) \geq D(q(x)\|p(x)) + D(q(y)\|p(y))$.


I don't think the given inequality is true (I am not sure about the reverse inequality). Recall that $$ D_{KL}(q(x,y)\| p(x,y))=\sum_{x\in \mathcal{X}}\sum_{y\in \mathcal{Y}} q(x,y)\log\bigg(\frac{q(x,y)}{p(x,y)}\bigg). $$ Consider non-identical joint distributions $p$ and $q$ over $\mathcal{X}\times\mathcal{X}$ (so $\mathcal{Y}=\mathcal{X}$), with $p(x,y)=q(x,y)=0$ for $y\neq x$ (so the supports of both distributions are on the diagonals). Then \begin{align} D_{KL}(q(x,y)\|p(x,y))&=\sum_{x_1\in \mathcal{X}}\sum_{x_2\in \mathcal{X}}q(x_1,x_2)\log\bigg(\frac{q(x_1,x_2)}{p(x_1,x_2)}\bigg)\\ &=\sum_{x\in \mathcal{X}} q(x)\log\bigg(\frac{q(x)}{p(x)}\bigg)\\ &=D_{KL}(q(x)\|p(x))=D_{KL}(q(y)\|p(y)). \end{align} In general, these are not all zero or infinite, so the stated inequality will not hold.

However, I think one can say that $$ D_{KL}(q(x,y)\|p(x,y))\geq \frac{D_{KL}(q(x)\|p(x))+D_{KL}(q(y)\|p(y))}{2}. $$ This should follow from the Chain Rule: \begin{align} D_{KL}(q(x,y)\|p(x,y))&=D_{KL}(q(x)\|p(x))+D_{KL}(q(y\vert x)\|p(y\vert x))\\ &=D_{KL}(q(y)\|p(y))+D_{KL}(q(x\vert y)\|p(x\vert y)), \end{align} summed twice and then using the nonnegativity of divergence.

| cite | improve this answer | |
  • $\begingroup$ You can improve from the average to the maximum, in your latest observation. This will help for $n\gg 2$. Also, the converse inequality cannot hold: consider $q$ uniform on $\{0,1\}^2$ and $p$ uniform on $\{(0,0),(1,1)\}$. $\endgroup$ – Clement C. Jun 29 '19 at 14:51
  • $\begingroup$ Thanks. The counter example I can think of is as follows: $\endgroup$ – Dawei Huang Jul 6 '19 at 2:04

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.