KL Divergence

Once you can measure the uncertainty in a single distribution with entropy, the natural next question is: how different are two distributions? Kullback-Leibler (KL) divergence answers it. Think of it as the penalty for being wrong: you believe the world follows a model $q$, but it actually follows $p$. KL divergence counts the extra bits of surprise you rack up, on average, by using the wrong distribution — the inefficiency of your model. It is the workhorse "distance" between distributions across statistics and machine learning, even though, as we'll see, it isn't quite a distance.

The formula

For a true distribution $p$ and a model $q$ over the same outcomes, the KL divergence from $q$ to $p$ is

$$D_{\mathrm{KL}}(p \,\|\, q) = \sum_i p_i \log_2 \frac{p_i}{q_i}.$$

Each $p_i$ is the true probability of outcome $i$, each $q_i$ is your model's probability for it, and $\log_2(p_i/q_i)$ is the per-outcome "extra surprise" — positive where your model under-weights an outcome, negative where it over-weights it. Weighting those by how often each outcome truly occurs (the $p_i$ out front) and summing gives the average extra cost. Two facts pin it down: it is always $\ge 0$, and it equals zero only when $q = p$ exactly. The bigger it is, the worse your model.

Worked example: the wrong coin

The truth is a fair coin, $p = (0.5, 0.5)$. Your model wrongly thinks it is biased, $q = (0.25, 0.75)$. How costly is that mistake?

$$D_{\mathrm{KL}}(p \,\|\, q) = 0.5\log_2\frac{0.5}{0.25} + 0.5\log_2\frac{0.5}{0.75} = 0.5(1) + 0.5(-0.585) = 0.208 \text{ bits}.$$

Now reverse the roles — pretend $q$ is the truth and $p$ the model:

$$D_{\mathrm{KL}}(q \,\|\, p) = 0.25\log_2\frac{0.25}{0.5} + 0.75\log_2\frac{0.75}{0.5} = 0.25(-1) + 0.75(0.585) = 0.188 \text{ bits}.$$

The two numbers differ — 0.208 versus 0.188. That is the point: KL divergence is not symmetric. "How wrong is $q$ about $p$" and "how wrong is $p$ about $q$" are genuinely different questions, and the direction you write matters.

Why it is everywhere

• It is what maximum likelihood minimizes. Fitting a model by maximum likelihood is exactly minimizing the KL divergence from your model to the data's empirical distribution. The "cross-entropy loss" that trains classifiers is the same quantity in disguise.
• It scores Bayesian updates. In Bayesian inference, the information a dataset provides is the KL divergence from the prior to the posterior, and variational methods and MCMC both lean on KL to measure how close an approximation is to the target.
• It underlies test power. The ability of a hypothesis test to tell two distributions apart grows with the KL divergence between them — more divergence, easier to distinguish.

KL divergence is the bridge from entropy to model-fitting: entropy measures the surprise inside one distribution, KL measures the surprise of swapping one distribution for another. That single idea shows up in nearly every corner of statistics, machine learning, and quantitative modeling.