Log-Sum Inequality

∑ a_i (a_i / b_i) ≥ (∑ a_i) ∑ a_i/∑ b_i — un-normalized KL.

The idea

Theorem (Log-sum inequality).

For non-negative numbers $a_1, \ldots, a_n$ and $b_1, \ldots, b_n$ with positive totals $A = \sum_i a_i$ and $B = \sum_i b_i$, $\sum_{i=1}^{n} a_i \log \frac{a_i}{b_i} \;\ge\; A \log \frac{A}{B},$ with equality if and only if the ratio $a_i / b_i$ is the same for every $i$.

The logarithm may be taken in any fixed base, since changing base multiplies both sides by the same constant.

The inequality follows from the convexity of $f(t) = t \log t$. Write the left side as $B \sum_i \frac{b_i}{B} f\!\left(\frac{a_i}{b_i}\right)$, a weighted average of $f$ at the ratios $a_i / b_i$ with weights $b_i / B$, and the right side as $B f(A/B)$, which is $f$ at the weighted average of those same ratios. By Jensen's inequality the average of $f$ is at least $f$ of the average, with equality only when the ratios all coincide. The figure shows why Jensen holds: a convex $f$ lies on or above its support line at the mean $\mu = \mathbb{E}[X]$, touching only at $(\mu, f(\mu))$, so averaging values of $f$ can only land at or above $f(\mu)$.

The $a_i$ and $b_i$ need not be probabilities. When both lists are distributions, $A = B = 1$ and the right side is $0$, which is the non-negativity of relative entropy; the log-sum inequality extends that fact to un-normalized weights.

Ways to work on it

• Walkthrough. State, verify, and use the log-sum inequality to deduce KL ≥ 0.
• Practice. Compare both sides of the log-sum inequality exactly.
• Hardest. Match each corollary of the log-sum inequality to the fact it proves.

Not sure where to start? Take the ten-question placement test.