I understand intuitively why cross-entropy is always bigger. However, could someone show that mathematically?
$\begingroup$
$\endgroup$
$\begingroup$
$\endgroup$
Let's say you have two distributions $p$ and $q$. Cross entropy is: $H(p,q)=-\sum_x{p(x)\log{q(x)}}$. First, you'll manipulate it to obtain the very well known form: $H(p,q)=H(p)+D_{KL}(p||q)$, where $D_{KL}(p||q)$ is called the KL distance.
$$H(p,q)=-\sum_x{p(x)\log{\left(\frac{q(x)p(x)}{p(x)}\right)}}=-\sum_xp(x)\log{\left(\frac{q(x)}{p(x)}\right)}-\sum_x{p(x)\log{p(x)}}=D_{KL}(p||q)+H(p)$$
Then, it only remains to prove that $D_{KL}(p,q)\geq 0$, which can be done in various ways. The page I shared uses $\log(x)\leq x-1$: $$D_{KL}(p||q)\geq \sum_x{p(x)\left(1-\frac{q(x)}{p(x)} \right)}=\sum_x{p(x)}-\sum_x{q(x)}=1-\sum_x{q(x)}\geq 0$$
From the beginning, we assume that $x$ is in the support set of $p(x)$, i.e. $p(x)$ is non-zero. In the wikipedia entry, it says $\sum_x{q(x)}=1$, but I disagree with it, since support set of $q(x)$ can be different.
