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

<p>However, I think one can say that 
<span class="math-container">$$
D_{KL}(q(x,y)\|p(x,y))\geq \frac{D_{KL}(q(x)\|p(x))+D_{KL}(q(y)\|p(y))}{2}.
$$</span>
This should follow from the <a href="https://www.cs.princeton.edu/courses/archive/fall11/cos597D/L03.pdf" rel="nofollow noreferrer">Chain Rule</a>:
<span class="math-container">\begin{align}
D_{KL}(q(x,y)\|p(x,y))&amp;=D_{KL}(q(x)\|p(x))+D_{KL}(q(y\vert x)\|p(y\vert x))\\
&amp;=D_{KL}(q(y)\|p(y))+D_{KL}(q(x\vert y)\|p(x\vert y)),
\end{align}</span>
summed twice and then using the nonnegativity of divergence.</p>

CC BY-SA 4.0
2019-06-29T14:51:24.207Z
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)\}$.
Clement C.
CC BY-SA 4.0
2019-07-06T02:04:19.617Z
Thanks. The counter example I can think of is as follows:
Dawei Huang
CC BY-SA 4.0
2019-06-29T03:16:00.567Z
2019-06-29T03:16:00.567Z
Jason Gaitonde
<p>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:</p>

<p><span class="math-container">$D(q(x,y)\|p(x,y)) \geq D(q(x)\|p(x)) + D(q(y)\|p(y))$</span>.</p>

<it.information-theory>
Chain rule for KL divergence
Dawei Huang
# Chain rule for KL divergence

(Asked by: username_0 on 2019-06-28)

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))$.

**Tags:** it.information-theory

---

## 1 answers

### Answer by username_1 on 2019-06-29. Score: 2

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](https://www.cs.princeton.edu/courses/archive/fall11/cos597D/L03.pdf):
\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.

> **Comments:**
> **username_2**: 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)\}$.  
> **username_0**: Thanks. The counter example I can think of is as follows:  

---

