# $\min D_\textrm{KL}(p(x_1,\dots,x_n) \mid\mid q_1(x_1)\cdots q_n(x_n))$ gives the marginals of $p(x_1,\dots,x_n)$?

Prove or disprove:

Let $p(x_1,\dots,x_n)$ be a given probability distribution over the $n$ variables $x_1, \dots,x_n$. The univariate probability distributions $q(x_1),\dots,q(x_n)$ that minimize the Kullback-Leibler divergence:

$$D_\textrm{KL}(p(x_1,\dots,x_n) \mid\mid q_1(x_1)\cdots q_n(x_n)) = \sum_{x_1,\dots,x_n}p(x_1,\dots,x_n)\log\frac{p(x_1,\dots,x_n)}{q_1(x_1)\cdots q_n(x_n)}$$

are the marginals of $p(x_1,\dots,x_n)$:

$$q_i(x_i) = p_i(x_i) = \sum_{\{x_j\}_{\backslash i}} p(x_1,\dots,x_n)$$

## 1 Answer

Using logarithmic identities, we can rewrite the KL divergence as $$\sum_{x_1, ..., x_n} p(x_1, ..., x_n) \log p(x_1, ..., x_n) - \sum_{i = 1}^n \sum_{x_1, ..., x_n} p(x_1, ..., x_n) \log q_i(x_i).$$

Note that only the second term depends on the univariate distributions over which we optimize, so we can focus on it and ignore the first term. For each $i$ we have

\begin{align} -\sum_{x_1, ..., x_n} p(x_1, ..., x_n) \log q_i(x_i) &= -\sum_{x_i} \sum_{x_1, ..., x_{i - 1}, x_{i + 1}, ..., x_n} p(x_1, ..., x_n) \log q_i(x_i) \\ &= -\sum_{x_i} p_i(x_i) \log q_i(x_i). \end{align}

Optimizing this quantity is equivalent to optimizing

$$\sum_{x_i} p_i(x_i) \log p_i(x_i) - \sum_{x_i} p_i(x_i) \log q_i(x_i) = D_\text{KL}(p_i(x_i) \mid\mid q_i(x_i)),$$

since the first term is again constant as a function of $q_i$. This KL divergence is minimal when $q_i(x_i) = p_i(x_i)$, proving that the optimal $q_i(x_i)$ is the marginal distribution $p_i(x_i)$.