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


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

  • $\begingroup$ Do we go from the second line to the third line $-\sum_{X_i} p_i(x_i)log q_i (x_i)$ because we're marginalizing out all of those other terms? $\endgroup$ – JoeTheShmoe 1 hour ago

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.