Defining entropy

Transcript: this stretch, timestamped

Everything before this page was setup. P02 built the moon robot and let three students race at encoding its instructions; P03 argued that perfect compression must look like random noise; P04 turned "perfect compression looks like random noise" into the definition information = log₂(1/p); P05 watched Shannon try to pin that quantity onto English by interviewing human brains. All of it has been about one event at a time. This stretch takes the last step — averaging — and in doing so produces the quantity the rest of the series runs on. Cross-entropy, in Part 2, is this formula with one slot swapped; KL divergence is the gap between the two. Get this page right and the rest are variations.

Outline, with timestamps

• 24:34 — The plan: three more expressions to rediscover, because modern ML runs on them.
• 25:05 — The question entropy asks: average information per symbol, for any symbol stream.
• 25:37 — Why that average is the compression limit — and why we already computed one, back at the robot.
• 26:10 — The formula written out, and the stacked-bar picture behind it.
• 26:43 — Entropy as total area; and the fine print — this is the i.i.d. case only.
• 27:13 — The name: von Neumann, statistical mechanics, and "nobody knows what entropy really is".
• 27:44 — Sloshing the distribution: even spreads are high entropy, spikes are low.
• 28:47 — The noiseless coding theorem: a floor you cannot beat and can always approach.
• 29:19 — Beyond i.i.d.: entropy rate of a stochastic process, and why language has no closed form.
• 30:21 — Roughly one bit per character of English, and the handoff to Parts 2 and 3.

25:05 — The averaging step, and why it is not trivial

Up to now the object of study has been a message: this string, with this probability, costs this many bits. Entropy changes the object of study to the source. The question is no longer "how expensive was that message?" but "how expensive is this source, per symbol, in the long run?" — answerable before a single symbol has been emitted, because it depends only on the distribution.

Mechanically the step is an expectation. Information is a function of the outcome, I(x) = log₂(1/p(x)); entropy is that function's expected value under the very distribution that defines it:

H(p) = E[ I(X) ] = Σ p(x) · log₂(1/p(x))   =  − Σ p(x) · log₂ p(x)
                    x                            x

The two forms are identical — log₂(1/p) = −log₂ p — and the only reason to prefer the first is that every term in it is visibly positive.

What makes this a real step rather than notation is the self-reference: p appears twice, once as the weight and once inside the log. That is exactly the structure that will fail to hold once cross-entropy arrives in Part 2, when the weights come from reality and the logs come from a model — and the difference between those two cases is the whole of cross-entropy. Notice it here, while both slots still hold the same thing.

The second thing worth noticing: entropy of a source made of independent symbols adds. Because logs turn products into sums, the information of an n-symbol message is the sum of the per-symbol informations, so its expected value is n·H(p). Averaging and concatenating commute. That is the property that lets a per-symbol number be a statement about arbitrarily long streams.

26:10 — The picture: probability along the base, information up the side

The animation on screen at this point is a genuinely good mental object and the captions can only gesture at it, so here it is in words. Lay the distribution out as one horizontal bar of total width 1, chopped into segments whose widths are the probabilities p(x) — they sum to 1 by construction. Now stand a rectangle on top of each segment whose height is that outcome's information, log₂(1/p(x)). Each rectangle has area p(x)·log₂(1/p(x)), one term of the sum. Entropy is the total area of the skyline.

The picture pays for itself immediately because the two dimensions fight each other. Squeeze a segment thinner and its rectangle grows taller — narrow means improbable means surprising. Widen it and the rectangle flattens toward zero height, because an outcome of probability 1 carries no information at all. Entropy is what survives that tug-of-war, and the reason it has an interior maximum rather than running off to infinity is precisely that neither dimension can win outright. (This particular visualisation is one Grant credits to Chris Olah's Visual Information Theory, linked in the video description — worth reading alongside.)

Check the two extremes by hand. As p → 0 the rectangle is infinitely tall but infinitesimally thin, and p·log₂(1/p) → 0 — so the convention 0·log 0 = 0 is not a fudge, it is the limit. At the other end a segment of width 1 gets height log₂ 1 = 0: a deterministic source has entropy exactly zero, because no bits are needed to transmit what the receiver already knows.

25:37 — The moon robot, closed out

The reason this stretch feels like a payoff rather than a definition is that you already computed an entropy in P02 without being told that was what you were doing. The clever student's weighted sum — half the time one bit, a quarter of the time two, the rest three — was Σ p·ℓ, the average code length. Entropy is Σ p·log₂(1/p), the average information. Those are the same arithmetic whenever ℓ(x) = log₂(1/p(x)) exactly, which is what a perfect code means. Here are the numbers side by side:

L = H exactly, and that equality is the certificate the third student was hunting for. The clever student's code is not "the best anyone has found"; it is provably unbeatable, because L can never go below H and here it already sits on the floor. Compare the naive fixed-length code at L = 2: the uniform distribution over four symbols has entropy log₂ 4 = 2 bits, so two bits per instruction is exactly right for a robot whose four commands are equally likely, and exactly 0.25 bits per instruction wasteful for this one.

28:47 — The theorem, stated precisely

Grant names it in a sentence and moves on, so here it is with the edges filled in. The result is Shannon's source coding theorem, also called the noiseless coding theorem — Theorem 9 of the 1948 paper. Two halves; the second is the surprising one.

Converse (the floor). For any uniquely decodable binary code with word lengths ℓ(x), the expected length satisfies

L = Σ p(x)·ℓ(x)  ≥  H(p)

with equality if and only if ℓ(x) = log₂(1/p(x)) for every x — which requires every probability to be a power of ½. One-line proof sketch (my addition, standard): Kraft's inequality says any prefix-free code obeys Z = Σ 2^(−ℓ(x)) ≤ 1. Define q(x) = 2^(−ℓ(x))/Z, a genuine distribution. Then L − H = D(p‖q) + log₂(1/Z), and both terms are non-negative — the first by Gibbs' inequality, the second because Z ≤ 1. So the gap between your code and the floor decomposes into "how wrong your implied model q is" plus "how much code space you left on the table". That first term is the KL divergence, arriving here two videos before it is formally introduced; it is not a coincidence that it shows up in the proof that entropy is a limit.

Achievability (the ceiling). Take ℓ(x) = ⌈log₂(1/p(x))⌉ — round each ideal length up to a whole number of bits. Those lengths satisfy Kraft, so a prefix code with them exists, and

H(p)  ≤  L  <  H(p) + 1

That one-bit bracket is the honest statement for a symbol-by-symbol code, and the leftover bit is pure rounding: you cannot spend 1.58 bits on a symbol, so you spend 2. The fix is to stop coding symbols and start coding blocks. Code N independent symbols at a time; the block has entropy N·H, the same bracket gives L_N < N·H + 1, and per symbol

H(p)  ≤  L_N / N  <  H(p) + 1/N   →   H(p)   as N → ∞

Shannon's own version of this is G_N ≤ H′ < G_N + 1/N where H′ is bits per symbol of the block code and G_N the N-block entropy rate. This is what "arbitrarily close" means, and it is also where the cost lives: approaching the limit requires buffering N symbols before you emit anything, so the price of optimality is latency. Arithmetic coding, which Part 3 of the series gets to, is the trick that gets the block-coding benefit without an exponentially large codebook.

27:44 — The shape of H: where the maximum is, and why

Grant spends this beat sloshing probability mass around a live graphic. The two facts he is demonstrating are worth stating as facts, because they are the ones you will use.

Two outcomes. With probabilities p and 1−p, entropy is the binary entropy function H₂(p) = p·log₂(1/p) + (1−p)·log₂(1/(1−p)). It is a symmetric dome pinned to zero at both ends and peaking at exactly 1 bit when p = ½. Shannon plots this as Fig. 7 of the 1948 paper. The shape is flatter near the top than most people expect:

A coin biased 60/40 still costs you 0.971 bits per flip — a 20-point skew buys under 3% compression. That flatness is why weak predictive edges are worth so little, and why the gains in text compression only arrive once a model is very confident.

n outcomes. Entropy is maximised by the uniform distribution and equals log₂ n there; it is minimised at zero by any point mass. Shannon lists this as property 2 of H. It follows in one line from Gibbs' inequality with q uniform, or from concavity plus symmetry via Jensen. Every entropy you will ever compute over n symbols therefore lives in [0, log₂ n], which is the sanity check to run first when a number looks wrong.

Both rules in the animation fall out of this: evening the mass out moves you toward uniform and up, spiking it moves you toward a point mass and down, and splitting the space into more symbols raises the ceiling log₂ n so there is more room to climb.

27:13 — The name, the story, and the thermodynamics

The anecdote Grant tells is one of the most repeated stories in science, and he is careful about it, so this page will be too.

"I looked into it, it's probably apocryphal, but there seems to be a grain of truth to this."— Grant Sanderson, 27:13

Here is the actual paper trail. The version everyone quotes appears in "Energy and Information" by Myron Tribus and Edward C. McIrvine, Scientific American vol. 225, no. 3 (September 1971) — the article linked in the video description. Tribus reports asking Shannon what he had been most concerned about, and quotes Shannon's reply: he had thought of calling the quantity "information", found the word overused, settled on "uncertainty", and then von Neumann told him to call it entropy "for two reasons. In the first place your uncertainty function has been used in statistical mechanics under that name, so it already has a name. In the second place, and more important, no one knows what entropy really is, so in a debate you will always have the advantage."

Note what that is and is not. It is a single source: one man's recollection, published roughly a decade after the conversation he is recalling, of a third party's remark made twenty years before that. There is no contemporaneous record, and Shannon's 1948 paper credits no one for the name. Repeat it as a good story with a plausible core — which is exactly how the video frames it — and not as documented history.

What is documented is the mathematical overlap, because Shannon states it himself, in the paragraph where he introduces H: the form −Σ pᵢ log pᵢ "will be recognized as that of entropy as defined in certain formulations of statistical mechanics", and "H is then, for example, the H in Boltzmann's famous H theorem." He footnotes Tolman's Principles of Statistical Mechanics. The Gibbs entropy of a system with microstate probabilities pᵢ is S = −k_B Σ pᵢ ln pᵢ, which is the same expression up to the choice of constant and log base; Boltzmann's S = k_B ln W is its uniform-distribution special case, the physics analogue of H = log₂ n. So the shared content is real and structural, not a pun.

What does not transfer is the word "disorder." That gloss is a thermodynamics-classroom shorthand and it actively misleads here. Information-theoretic entropy is a property of a probability distribution, not of an arrangement of matter, and it measures one thing only: how many yes/no answers, on average, it takes to pin down a draw from that distribution. A perfectly tidy stack of cards in a known order has entropy zero; the same stack shuffled has entropy log₂(52!) ≈ 225.6 bits — but the bits are in your uncertainty about the order, not in the cards. Nothing physical changed about the cardboard. If you catch yourself reasoning from "entropy means disorder" to a claim about a message, stop; the correct chain is always "entropy means expected surprise means bits."

29:19 — Where the tidy formula stops, and language begins

The fine print Grant flags at 26:43 and returns to here is easy to skate past, and it is the whole reason the series continues. H(p) = Σ p·log₂(1/p) is the compression limit only when every symbol is drawn independently from the same distribution. True for the moon robot by construction; flagrantly false for English, where the distribution over the next character depends on everything before it.

The general object is the entropy rate of a stochastic process — the average information per symbol as the message length goes to infinity:

H(X) = lim (1/n) · H(X₁, X₂, …, Xₙ)      as n → ∞

Same question, different average: you are now averaging over whole messages rather than over one distribution. For a source with memory this is strictly less than the entropy of its marginal letter frequencies, because context does work that single-symbol statistics cannot see. And for English there is no formula to evaluate — there is no closed-form probability distribution for language, which is why Shannon had to go and interview people (P05) rather than run a function over a corpus.

The number he arrived at, and the number Grant quotes here: with about 100 characters of preceding context, the entropy of English is on the order of one bit per character. Grant's framing is right that this sounds absurd — one yes/no answer per letter. For scale, Shannon's own ladder in Prediction and Entropy of Printed English (1951) runs: log₂ 26 = 4.7 bits per letter if letters were equiprobable; 4.14 bits once you use letter frequencies alone; roughly 2.3 bits using statistics spanning up to eight letters; and "something of the order of one bit per letter" once long-range structure up to 100 letters is in play — a redundancy of roughly 75%. Three quarters of written English is, in the information-theoretic sense, already implied by its own context.

That estimate is the hinge of the whole trilogy. It is a claim about compressibility that can only be established by something that understands English, which in 1951 meant a human brain and today means a language model. Part 2 picks it up from the modelling side — what happens when the distribution you code against is a model's guess rather than the truth — and Part 3 cashes it out with an actual algorithm that gets close to the bound in practice.

Where people get stuck

"Is it log(1/p) or −log p?" They are the same number and both are non-negative for p ∈ (0,1]. The minus sign in H = −Σ p log p is not a sign convention with hidden meaning; it is there because log p of a probability is negative and entropy is a count of bits. If a negative entropy ever appears in your output for a discrete distribution, you have a bug, not a discovery. (Differential entropy of a continuous density genuinely can be negative — but that is a different quantity that happens to share the name, and nothing on this page applies to it unchanged.)

"1.75 bits" — a symbol can't be three-quarters of a bit. Correct, and nobody claims it can. H is a rate, not a per-message length: 1.75 bits per instruction means 1750 bits for 1000 instructions. Fractional per-symbol costs are realisable in aggregate precisely because coding long blocks amortises the rounding — that is the content of the 1/N term in L_N/N < H + 1/N. The moon robot only hits an integer per symbol because its probabilities are powers of ½.

Confusing "entropy is high" with "the data is complicated." Entropy is high when the distribution is spread out, which for a fixed alphabet means near-uniform. A stream of uniform random bytes has maximal entropy and no structure whatsoever. Complexity and entropy are different axes — the quantity that tries to capture "complicated" is Kolmogorov complexity, which is a property of a string rather than a distribution, and is uncomputable. Shannon entropy is the tractable one, and it is tractable exactly because it asks less.

Reading the theorem as a promise about your file. The bound is on the expected length under the source distribution. Any individual message can compress far better or far worse; and a code hand-tuned to one specific file can beat H on that file while losing on average. "No code beats entropy" is an average-case statement, and it needs the source distribution you claimed to be the source distribution you actually have — which, for English, is the thing nobody has.

Going deeper, verified

• A Mathematical Theory of Communication — Claude E. Shannon (1948) · Linked in the video description. §6 defines H and lists its properties (including the log n maximum and Fig. 7, the binary entropy curve); §9 proves Theorem 9, the noiseless coding theorem; §10 works the ½, ¼, ⅛, ⅛ example that became the moon robot.
• Prediction and Entropy of Printed English — Claude E. Shannon (1951) · Linked in the video description. The source of the "about one bit per character" figure and of the 4.7 → 4.14 → 2.3 → ~1 ladder quoted above.
• Energy and Information — Myron Tribus & Edward C. McIrvine, Scientific American 225(3), pp. 179–190 (1971) · Linked in the video description. The one primary source for the von Neumann naming story; read it to see exactly how thin the sourcing is.
• Visual Information Theory — Christopher Olah (2015) · The origin of the area-of-rectangles picture Grant credits in the description; carries the same visual through cross-entropy and KL, so it doubles as a preview of Part 2.
• Information Theory, Inference, and Learning Algorithms — David J. C. MacKay (2003), free full text · Chapters 4–5 give the textbook treatment of everything on this page: the source coding theorem in both its symbol-code and block forms, Kraft's inequality, Gibbs' inequality, and Huffman's construction — the constructive answer to "how do I actually build the optimal code?", which the video does not cover.

Exercises

1. Beat the bracket. Take the distribution (0.4, 0.3, 0.2, 0.1). Compute H to three decimals. Then build a Huffman code by hand and compute its L. A good answer reports both numbers, confirms H ≤ L < H+1, and says how many bits per symbol are being lost to integer rounding. Then repeat on pairs of symbols (16 blocks, probabilities being products) and show the per-symbol loss roughly halves.
2. Redundancy of your own text. Take any English file of a few hundred KB. Compute the letter-frequency entropy H₁ over the 26 letters plus space, and the redundancy 1 − H₁/log₂ 27. A good answer gets H₁ somewhere near 4 bits per character and notes that this is a ceiling on the true entropy rate, not an estimate of it — then compares against what gzip actually achieves on the same file and explains why gzip does better than H₁ without violating any theorem.
3. Where the dome is flat. Plot H₂(p) for p ∈ (0,1) and find, numerically, the largest p for which H₂(p) ≥ 0.99. A good answer gives the number and draws the moral: state how much better than chance a binary predictor must be before it buys you even 1% compression.