Kullback-Leibler Divergence

Let $p$ and $q$ be two probability distributions of a random variable $X$. Formally, let $X\sim p_X(x)$ and $X\sim q_X(x)$, or by common abuse of notation, $X\sim p(x)$ and $X\sim q(x)$. The Kullback-Leibler (KL) divergence, also known as relative entropy, measures the statistical discrepancy between these two distributions.

Definition

The KL divergence from $q$ to $p$ is defined as:

$$D_{KL}(p\parallel q)=\{\begin{array}{ll}{\mathbb{E}}_p\left[{\log }_2\frac{p(X)}{q(X)}\right]& \text{if }p\ll q\\ +\infty & \text{otherwise}\end{array}$$

Absolute Continuity ($p\ll q$)

The condition $p\ll q$ signifies that the distribution $p$ is absolutely continuous with respect to $q$, meaning $q$ dominates $p$. Formally, for every $x\in {\mathcal{A}}_{\mathcal{X}}$: $q(x)=0⟹p(x)=0$ This ensures the Radon-Nikodym derivative exists and the ratio $\frac{p(x)}{q(x)}$ is well-defined. If $q(x)=0$ and $p(x)=0$, the contribution to the expectation is conventionally taken as $0$.

The Singularity Case ("Otherwise")

The “otherwise” condition occurs when absolute continuity is violated. This happens if there exists at least one $x\in \mathcal{X}$ such that: $\exists x\in {\mathcal{A}}_{\mathcal{X}}:q(x)=0\text{and}p(x)>0$ In this scenario, the support of $p$ is not contained within the support of $q$. The “surprise” of observing $x$ under $q$ when it has a positive probability under $p$ is infinite, hence $D_{KL}(p\parallel q)=\infty$.

---

Properties

While $D_{KL}(p\parallel q)$ is often used to quantify the “distance” between distributions, it is strictly a divergence and not a metric (distance) in the topological sense.

1. Asymmetry

The KL divergence is non-symmetric. In general:

$$D_{KL}(p\parallel q)\ne D_{KL}(q\parallel p)$$

The information loss incurred when using $q$ to model $p$ is not necessarily equal to the loss incurred when using $p$ to model $q$. While specific cases exist where equality holds (e.g., if $p=q$, then both equal $0$), it remains a directed measure.

2. Violation of the Triangle Inequality

A true distance must satisfy the triangle inequality. For any three distributions $p,q,r$, the following does not necessarily hold:

$$D_{KL}(p\parallel r)\le D_{KL}(p\parallel q)+D_{KL}(q\parallel r)$$

Because $D_{KL}$ does not respect this geometric constraint, it cannot define a standard metric space.

3. Non-negativity (Gibbs’ Inequality)

Despite not being a distance, $D_{KL}$ is always non-negative:

$$D_{KL}(p\parallel q)\ge 0$$

with $D_{KL}(p\parallel q)=0$ if and only if $p=q$ almost everywhere. This property stems from Jensen’s Inequality applied to the logarithmic function.

Proof of $D_{KL}(p\parallel q)\ge 0$

Let $X$ be a random variable with support ${\mathcal{A}}_{\mathcal{X}}$. We wish to show that $-D_{KL}(p\parallel q)\le 0$.

Starting from the definition:

$$-D_{KL}(p\parallel q)=-{\mathbb{E}}_p\left[{\log }_2\frac{p(X)}{q(X)}\right]={\mathbb{E}}_p\left[{\log }_2\frac{q(X)}{p(X)}\right]$$

Expanding the expectation for the discrete case (the continuous case follows analogously via integration):

$${\mathbb{E}}_p\left[{\log }_2\frac{q(X)}{p(X)}\right]=\sum _{x\in {\mathcal{A}}_{\mathcal{X}}}p(x){\log }_2\frac{q(x)}{p(x)}$$

Since the logarithm function is strictly concave, we can apply Jensen’s Inequality, which states that for a concave function $f$:

$$\mathbb{E}[f(Y)]\le f(\mathbb{E}[Y])$$

Substituting $f={\log }_2$ and $Y=\frac{q(X)}{p(X)}$:

$$\sum _{x\in {\mathcal{A}}_{\mathcal{X}}}p(x){\log }_2\frac{q(x)}{p(x)}\le {\log }_2\left(\sum _{x\in {\mathcal{A}}_{\mathcal{X}}}p(x)\frac{q(x)}{p(x)}\right)$$

The term inside the logarithm simplifies to the total sum of the probability distribution $q$:

$$\sum _{x\in {\mathcal{A}}_{\mathcal{X}}}q(x)=1$$

Thus, we obtain:

$$-D_{KL}(p\parallel q)\le {\log }_2(1)=0$$

Multiplying by $-1$ reverses the inequality:

$$D_{KL}(p\parallel q)\ge 0$$

Equality Condition: Since ${\log }_2$ is strictly concave, equality holds if and only if the ratio $\frac{q(x)}{p(x)}$ is constant for all $x$. Given that both are normalized probability distributions, this constant must be $1$, implying $p(x)=q(x)$ almost everywhere.