Visual walkthrough — Entropy and KL divergence

This page rebuilds the central result of the parent topic — the KL divergence formula — starting from nothing but a coin and a question. We draw every step. By the end you will see why

$$\begin{gathered} D_{KL}(p \\ |q)={\sum }_{x}p(x)\log \frac{p(x)}{q(x)} \end{gathered}$$

is exactly "the extra bits you waste when you believe the wrong story about the world."

Nothing here assumes you know what a logarithm is for, what "bits" mean, or why we sum. We build each piece on a picture first.

---

Step 1 — What is a "message" and why do we count bits?

WHAT we set up: a random outcome (a coin, a die, a weather label) and a rule that turns each possible outcome into a string of 0s and 1s. That rule is a code.

WHY we care: fewer bits = cheaper messages = better compression = (later) better loss functions. Every quantity on this page is secretly a bit count.

PICTURE: below, four possible outcomes each get a little binary tag. Count how many yes/no splits it takes to reach each leaf — that count is the bit-length of that outcome.

---

Step 2 — Why the best length for outcome $x$ is $-{\log }_{2}p(x)$

Here the logarithm enters. We must justify why the log, and not some other function.

WHAT we claim: if outcome $x$ happens with probability $p(x)$, the shortest possible average code gives it a length of

$\underset{\text{bits for }x}{\underbrace{\ell (x)}}=\underset{\text{"surprisal"}}{\underbrace{-{\log }_{2}p(x)}}.$

WHY the log? Each yes/no split cuts the number of still-possible outcomes roughly in half. To pin down one outcome out of $n$ equally likely ones you need to halve $n$ down to $1$ — that is ${\log }_{2}n$ halvings. If an outcome has probability $p$, it behaves like one choice out of $\frac{1}{p}$ equally likely ones, so it needs ${\log }_2\frac{1}{p}=-{\log }_{2}p$ splits. The log is literally "how many times can I halve until I'm sure?" No other function counts halvings.

Read the formula term by term:

• $p(x)$ — how common outcome $x$ is. Big $p$ → common → few bits.
• $\frac{1}{p(x)}$ — "one in how many" this outcome feels like.
• ${\log }_2$ — converts "one in how many" into "how many yes/no halvings."
• the minus sign — because $p\le 1$ makes ${\log }_{2}p$ negative; we flip it so lengths come out positive.

PICTURE: the curve $-{\log }_{2}p$. Certain events ($p=1$) sit at height $0$ — no bits, no surprise. Rare events shoot up.

---

Step 3 — Averaging the surprises gives entropy $H(p)$

WHAT we do: outcomes don't all cost the same, so we take the average bit-length, weighting each outcome by how often it actually occurs.

$H(p)=\underset{\text{add over all outcomes}}{\underbrace{\sum _x}}\underset{\text{how often }x\text{ happens}}{\underbrace{p(x)}}\cdot \underset{\text{its bit-length}}{\underbrace{(-{\log }_{2}p(x))}}.$

WHY weight by $p(x)$? Because a rare outcome is expensive but seldom sent, so it should count little in the long-run average. "Expected value" = probability-weighted sum. That is exactly what the ${\sum }_{x}p(x)(\cdots )$ pattern means.

PICTURE: bars of surprisal height $-{\log }_{2}p(x)$, each shrunk by its width $p(x)$; the shaded total area is $H(p)$ — the average message length if you use the best code for $p$.

---

Step 4 — The mistake: coding for $q$ when reality is $p$

Now the twist that creates KL divergence.

WHAT happens: you believe the outcomes follow a distribution $q$ (your model, your guess). So you build the optimal code for $q$: outcome $x$ gets length $-{\log }_{2}q(x)$. But reality actually follows $p$. Your messages still get sent at whatever frequency $p$ dictates.

WHY this matters: your bit-lengths come from $q$, but the how-often weighting comes from $p$. Average length is now

$H(p,q)={\sum }_x\underset{\text{real frequency}}{\underbrace{p(x)}}\cdot \underset{\text{length from your wrong code}}{\underbrace{(-{\log }_{2}q(x))}}.$

This mismatched average is the cross-entropy $H(p,q)$.

PICTURE: two codes side by side for the same outcomes. The left (blue) is built for $q$ — it makes the outcome $q$ thinks is common short. But reality (pink bars, following $p$) sends a different outcome most often, so on the wrong code the frequent real outcome landed on a long branch. Wasted length in yellow.

---

Step 5 — Subtract: the waste is KL divergence

WHAT we compute: the extra bits you pay for using the wrong code = (what you actually paid) − (the best you could have paid).

$$\begin{gathered} D_{KL}(p \\ |q)=\underset{\text{paid with }q\text{’s code}}{\underbrace{H(p,q)}}-\underset{\text{best, with }p\text{’s code}}{\underbrace{H(p)}}. \end{gathered}$$

WHY subtract? Because "waste" only makes sense relative to the best possible. Both terms are average bit-lengths under the same real frequencies $p$; their difference is the pure penalty of your wrong belief.

Now expand both and watch the terms combine:

$$\begin{gathered} D_{KL}(p \\ |q)=(-{\sum }_{x}p(x){\log }_{2}q(x))-(-{\sum }_{x}p(x){\log }_{2}p(x)) \end{gathered}$$

Pull the common $p(x)$ and the common sum together:

$={\sum }_{x}p(x)\left[\underset{\text{one log of a ratio}}{\underbrace{{\log }_{2}p(x)-{\log }_{2}q(x)}}\right]={\sum }_{x}p(x){\log }_2\frac{p(x)}{q(x)}.$

The bracket used one rule: $\log a-\log b=\log \frac{a}{b}$ — subtracting logs = dividing inside. That is the whole algebra.

PICTURE: the tall cross-entropy bar minus the shorter entropy bar; the leftover slab (yellow) is $D_{KL}$ — the extra bits, term by term.

Term-by-term, right where each symbol lives:

• $p(x)$ (outside) — real frequency: penalties for outcomes that never really happen are ignored.
• $\frac{p(x)}{q(x)}$ — "how much more (or less) common reality is than your model thinks."
• ${\log }_2$ — turns that ratio into bits; ratio $=1$ (you were right) → ${\log }_{2}1=0$ → no penalty.

---

Step 6 — Why it is never negative (a picture of Jensen)

WHAT we prove: $$\begin{gathered} D_{KL}(p \\ |q)\ge 0 \end{gathered}$$, and it's $0$ only when $q=p$ everywhere. You can never save bits by being wrong.

WHY believe it? Flip the ratio and use one fact about the log curve: $\log$ is concave (bends downward, like a frown). For a concave curve, the average of the curve's heights sits below the curve above the average input — that's Jensen's inequality.

$$\begin{gathered} D_{KL}(p \\ |q)=-{\sum }_{x}p(x){\log }_2\frac{q(x)}{p(x)}\ge -{\log }_2(\underset{={\sum }_{x}q(x)=1}{\underbrace{\sum _{x}p(x)\frac{q(x)}{p(x)}}})=-{\log }_{2}1=0. \end{gathered}$$

The $p(x)$ cancels the $p(x)$ in the denominator, leaving ${\sum }_{x}q(x)=1$ because $q$ is a probability distribution. So the whole thing is $\ge -{\log }_{2}1=0$.

PICTURE: the concave $\log$ curve; a straight chord below it; the gap between "average of heights" and "height of average" is exactly the KL penalty — it closes to zero only when all the ratios equal $1$.

Recall Why zero only when p = q

When does equality hold in Jensen ::: When the input $\frac{q(x)}{p(x)}$ is the same constant for every $x$; since both sum to 1, that constant is 1, i.e. $q=p$.

---

Step 7 — The degenerate cases (never let the reader get stuck)

Formulas break at zeros. Here is every edge, drawn.

PICTURE: the ratio-to-penalty curve ${\log }_{2}r$ with the three regimes marked: $r=1$ pit of zero penalty, $r\to \infty$ (model too confident against reality) rising, and the $q=0$ wall at $+\infty$.

---

Step 8 — Numbers on the picture (worked, both directions)

---

The one-picture summary

Everything above is one subtraction: your average message length (using the wrong story $q$) minus the shortest possible length (the true story $p$). The leftover is $D_{KL}$.

Recall Feynman retelling (say it out loud)

A friend keeps sending you coin results as yes/no answers. If you knew the true odds $p$, you'd design a codebook that gives common outcomes short tags — your bill averages $H(p)$ bits, the cheapest possible. But you only guessed the odds $q$, so you built the codebook for $q$. Reality still sends outcomes at rate $p$, so your bill is now $H(p,q)$, which is bigger whenever your guess was off. The overcharge — the wasted bits from believing the wrong story — is $$\begin{gathered} D_{KL}(p \\ |q)={\sum }_{x}p(x){\log }_2\frac{p(x)}{q(x)} \end{gathered}$$. It's never negative (you can't beat the true codebook — Jensen guarantees it), it's exactly zero only when your guess was perfect, it explodes to infinity if you bet zero on something that actually happens, and it is not symmetric because the overcharge depends on who's actually flipping. Minimizing this overcharge is what training a classifier, an ELBO, or a VAE is quietly doing.

Where this goes next: Mutual Information (KL between a joint and its independent copy), Maximum Entropy Principle (Step 3 pushed to its limit), Information Gain (entropy drop from a split), and F-divergences (KL as one member of a whole family).