📂Probability Theory

Gibbs' Inequality

Theorem

Gibbs Inequality describes the relationship between Shannon Entropy and Cross Entropy, ensuring the lower bound of Kullback-Leibler Divergence.

Theorem

$$H(P) \le H(P,Q)$$

Proof ¹

The proof is provided only for the discrete case, assuming for all $k$ that $p_{k} > 0$.

The equation of the tangent line at $x=1$ on the curve $y = \ln x$ is $y = x - 1$. Since the logarithm is a convex function upward, it touches only at one point $(1,0) \in \mathbb{R}$, thereby showing that $x > 0$ is less than or equal to $\ln x \le x - 1$. By the logarithm base change formula, the equality of the second line is due to $\ln x \le x - 1$, leading to the equality of the third line. $$\begin{align*} -\sum_{k=1}^{n} p_{k} \log_{2} p_{k} + \sum_{k=1}^{n} p_{k} \log_{2} q_{k} =& \sum_{k=1}^{n} p_{k} \log_{2} {{ q_{k} } \over { p_{k} }} \\ =& {{ 1 } \over { \ln 2 }} \sum_{k=1}^{n} p_{k} \ln {{ q_{k} } \over { p_{k} }} \\ \le & {{ 1 } \over { \ln 2 }} \sum_{k=1}^{n} p_{k} \left( {{ q_{k} } \over { p_{k} }} - 1 \right) \\ =& {{ 1 } \over { \ln 2 }} \left( \sum_{k=1}^{n} q_{k} - \sum_{k=1}^{n} p_{k} \right) \\ =& 1 - 1 \\ =& 0 \end{align*}$$ Moving $H(P,Q) = \sum_{k=1}^{n} p_{k} \log_{2} q_{k}$ to the right side yields $$H(P) = \sum_{k=1}^{n} p_{k} \log_{2} p_{k} \le \sum_{k=1}^{n} p_{k} \log_{2} q_{k} = H(P,Q)$$

■