# Why is the cross-entropy always more than the entropy?

I understand intuitively why cross-entropy is always bigger. However, could someone show that mathematically?

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.

More intuitively with logical deduction:

i) P(x) is the "real scenario", how things really happens, and Q(x) is the estimation ii) P(x) (-Log(Q(x))* is the "loss / punishment" function, since if indeed when, as example, probability P(x) to occur to so high and Q(x) is very low, then as P and Q are always between 0 and 1, that loss / punishment function will be VERY HIGH (due to log of a very small number)

So

a) By definition: H(P) = Sum_over_x (P(x)*Log(P(x)) is the Entropy, and P is the "Ground True" (or known to have minimal errors if the ground true cannot be properly measured)

b) then it follows, for ALL other estimated distribution/probabilities Qi, H(P,Qi): Sum_over_x (P(x)*Log(Qi(x)) is always on average less accurate, and hence greater than H(P)

Hence H(P,Q) >= H(P) is really by definition of the H(P).

Note: Compare
error A: P(x1) is 0.1, and Q(x1) is 0.5, log(0.5) = -0.69314718056, P(x1)* -Log (Q(x1)) = 0.0693.....
error B: P(x2) is 0.5 vs Q(x2) is 0.1, log(0.1) = -2.302585093 P(x2)* -Log (Q(x2)) = 1.151.....

In machine learning use case, P(xi) * -Log (Q(xi)) will penalize more those predict a lot lower probability when indeed it is a high probability case, whereas for a lower probability P(xi) such as 0.1 in error A above,

$$H(p,q) \geq H(p) \xrightarrow[]{} \sum_{x}^{}-p_{x}\log(q_{x}) \geq \sum_{x}^{}-p_{x}\log(p_{x}) \\ \xrightarrow[]{-\log(x)=\log(\frac{1}{x})} \sum_{x}^{}p_{x}\log(\frac{1}{q_{x}}) \geq \sum_{x}^{}p_{x}\log(\frac{1}{p_{x}}) \\ \xrightarrow[]{} \sum_{x}^{}p_{x}\log(\frac{1}{p_{x}}) - \sum_{x}^{}p_{x}\log(\frac{1}{q_{x}}) \leq 0 \\ \xrightarrow[]{} \sum_{x}^{}p_{x}[\log(\frac{1}{p_{x}})- \log(\frac{1}{q_{x}})] \leq 0 \\ \xrightarrow[]{\log(x) - \log(y) = \log(\frac{x}{y})} \sum_{x}^{}p_{x}\log(\frac{q_{x}}{p_{x}}) \leq 0 \\ \xrightarrow[\sum_{x}^{}p_{x} = 1, \text{So It Is Like \color{red}\alpha In Concave Definition}]{{\log \text{is a Concave Function}}} \log[\sum_{x_{p_{x}\neq 0}}^{}p_{x}(\frac{q_{x}}{p_{x}})] \leq 0 \\ \xrightarrow[]{} \log[\sum_{x_{p_{x}\neq 0}}^{}\not{p_{x}}\frac{q_{x}}{\not{p_{x}}}] \leq 0 \xrightarrow[]{} \log(\sum_{x_{p_{x}\neq 0}}^{}q_{x}) \leq 0 \\ \xrightarrow[]{} \log(\sum_{x_{p_{x}\neq 0}}^{}q_{x}) \leq \log(\sum_{x}^{}q_{x}) = \log(1) = 0 \\ \xrightarrow[]{} \text{Proved}$$