Index: The Book of Statistical Proofs ▷ General Theorems ▷ Information theory ▷ Kullback-Leibler divergence ▷ Non-negativity

Theorem: The Kullback-Leibler divergence is always non-negative

\[\label{eq:KL-nonneg} \mathrm{KL}[P||Q] \geq 0\]

with $\mathrm{KL}[P \vert \vert Q] = 0$, if and only if $P = Q$.

Proof: The discrete Kullback-Leibler divergence is defined as

\[\label{eq:KL} \mathrm{KL}[P||Q] = \sum_{x \in \mathcal{X}} p(x) \cdot \log \frac{p(x)}{q(x)}\]

which can be reformulated into

\[\label{eq:KL-dev} \mathrm{KL}[P||Q] = \sum_{x \in \mathcal{X}} p(x) \cdot \log p(x) - \sum_{x \in \mathcal{X}} p(x) \cdot \log q(x) \; .\]

Gibbs’ inequality states that the entropy of a probability distribution is always less than or equal to the cross-entropy with another probability distribution – with equality only if the distributions are identical –,

\[\label{eq:Gibbs-ineq} - \sum_{i=1}^n p(x_i) \, \log p(x_i) \leq - \sum_{i=1}^n p(x_i) \, \log q(x_i)\]

which can be reformulated into

\[\label{eq:Gibbs-ineq-dev} \sum_{i=1}^n p(x_i) \, \log p(x_i) - \sum_{i=1}^n p(x_i) \, \log q(x_i) \geq 0 \; .\]

Applying \eqref{eq:Gibbs-ineq-dev} to \eqref{eq:KL-dev}, this proves equation \eqref{eq:KL-nonneg}.

∎
Sources:

Metadata: ID: P117 | shortcut: kl-nonneg | author: JoramSoch | date: 2020-05-31, 23:43.