= Solution
Use base-two logarithms throughout, so information and entropy are in bits. The <relative entropy> of classical probability distributions is
$$
D(p\|q)=\sum_{x:p(x)>0}p(x)\log_2\frac{p(x)}{q(x)}.
$$
Set $0\log_2(0/q)=0$; if $p(x)>0$ and $q(x)=0$, define the value to be $+\infty$. In the finite case, $\ln u\leq u-1$ gives
$$
\begin{aligned}
(\ln2)D(p\|q)
&=-\sum_{x\in\operatorname{supp}p}p(x)\ln\frac{q(x)}{p(x)}\\
&\geq\sum_{x\in\operatorname{supp}p}[p(x)-q(x)]
=1-q(\operatorname{supp}p)\geq0.
\end{aligned}
$$
Hence \b[$D(p\|q)\geq0$], with equality exactly when $p=q$: equality in the logarithm inequality requires $q(x)=p(x)$ on the support, and equality in the last step leaves no mass outside it.
Back to article page
