# Chain rule for KL divergence

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.
• 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)\}$. Jun 29 '19 at 14:51