Defining information: why log(1/p) and nothing else

Transcript: this stretch, timestamped

P03 argued that a perfect compressor's output must look like random noise, and squeezed a hard consequence out of that: if every n-bit output is equally likely, the messages producing them each had probability 2⁻ⁿ. That is a statement about a very special case — clean dyadic probabilities, the robot with its four instructions. This page is where the special case gets promoted into a general-purpose quantity that survives messy probabilities, and where the units “bits” get attached to numbers like 4.19. P05 then puts the definition under real load, on the probabilities of English letters, where nothing is a power of two and nothing is independent.

Outline, with timestamps

• 14:47 — Insight becomes definition: a message given n bits by a perfect scheme has probability 2⁻ⁿ.
• 15:07 — Take the log and negate: bits allocated = −log₂ p. Grant calls this the fundamental formula of information theory.
• 15:39 — How to read it: how many times you halve the space of possibilities. The graph, and three interchangeable notations.
• 16:09 — Shannon's move: keep the expression when p is not a power of two, accept fractional output, and define it to be the information of an event.
• 16:40 — The picture: a bar that grows as probability is squeezed toward zero. And a warning that this is more than a change of units.
• 17:10 — What is actually being claimed: information is a lower bound on compressed size, once you average over messages.

From “n bits” to “probability 2⁻ⁿ”, and back 14:47

The whole page turns on one algebraic step, so it is worth writing both directions out. P03's conclusion was a statement about probabilities, given a code:

perfect code assigns message x exactly n bits   ⟹   p(x) = 2⁻ⁿ

Solve for n instead of p. Take log₂ of both sides: log₂ p = −n, so n = −log₂ p = log₂(1/p). Nothing has been assumed that was not already there; the same fact is simply being read in the other direction, as a rule that hands you a length when you hand it a probability.

length of x under a perfect code   =   −log₂ p(x)   =   log₂(1/p(x))

This is the move the video's introduction promises — an insight leading you to a definition rather than a definition being dropped on you. Note carefully what it is not: it is not a claim that you can build such a code for arbitrary probabilities. In the robot example the four instructions had probabilities ½, ¼, ⅛, ⅛, and the clever student's code words were 1, 2, 3, 3 bits long. The equation holds on the nose there because the probabilities were rigged to be powers of two. The question that drives the rest of this stretch is what to do when they are not.

Reading −log₂ p without flinching 15:39

Three expressions appear in the wild and they are all the same function on 0 < p ≤ 1:

−log₂ p   =   log₂(1/p)   =   log_½ p

The first two are the same because log(1/p) = log 1 − log p = −log p. The third is the change-of-base identity log_b a = log₂ a / log₂ b with b = ½, whose log₂ is −1. Grant notes he has never seen anyone lean into the base-½ form, and is personally partial to it 16:09 — it is the one where the counting interpretation is written directly into the notation.

That interpretation is the useful mental image:

"the intuitive way to read it is that it's asking how many times do you chop your space of possibilities in half to get to a certain quantity"— Grant Sanderson, 15:39

Halve a space three times and you are down to an eighth of it, which is why p = ⅛ costs three bits. The curve you get has exactly the shape the interpretation demands: it is 0 at p = 1 (a certainty costs nothing to announce), strictly decreasing, unbounded as p → 0, and convex. Convexity is worth registering now; it is the property that makes Jensen's inequality bite once this becomes cross-entropy, later in the trilogy.

Why a logarithm and nothing else 16:09

The video gets to −log p through compression; the argument in this section is the standard textbook route to the same place, added here because it is what makes the definition feel forced rather than merely convenient. Suppose you had never heard of codes and simply asked what a measure of “how informative is this event” must satisfy. Write it I(p), a function of the event's probability alone.

• Certainty is free. I(1) = 0. Being told the sun rose tells you nothing.
• Rarer is more informative. I is non-increasing in p.
• Independent events add. If A and B are independent then p(A ∧ B) = p(A)·p(B), and learning both should cost the sum of learning each: I(p·q) = I(p) + I(q).

The third axiom is the load-bearing one, and it is exactly the demand that a function turn multiplication into addition. Substitute p = e⁻ᵘ and define g(u) = I(e⁻ᵘ); the condition becomes g(u + v) = g(u) + g(v), which is Cauchy's functional equation. Its only continuous solutions are the linear ones, g(u) = c·u, giving

I(p) = −c · ln p = c′ · log_b(1/p)      for some constant c′ > 0

Be honest about where the work is being done. Cauchy's equation, with no regularity assumption at all, has monstrous solutions built from a Hamel basis of the reals over the rationals — everywhere-discontinuous, unbounded on every interval. What kills them is any one of several mild conditions: continuity, monotonicity, measurability, or boundedness on some interval. Monotonicity is already among our axioms, so the conclusion stands, but the sketch above is a derivation with an assumption in it, not a proof from nothing. (Shannon's own uniqueness theorem, Theorem 2 and Appendix 2 of the 1948 paper, is the analogous result one level up: it pins down the entropy H = −K Σ p log p from continuity, a monotonicity condition on the uniform case, and a grouping axiom.)

What survives is a one-parameter family, and the parameter is nothing but the choice of unit. Fixing the base fixes the name: base 2 gives bits, base e gives nats, base 10 gives hartleys (also “bans”). Choosing base 2 is not a mathematical decision, it is the decision to measure in binary yes-or-no answers — which is precisely what the compression story was doing all along. Two independent roads, one formula.

One caveat on the additivity axiom: it is stated for independent events. Nothing breaks for dependent ones, but the addition then runs through conditional probabilities via the chain rule, which is how the video handles English a few minutes later, 19:50.

The scale, in numbers

The formula is worth internalising as a scale rather than a symbol. A halving is one bit; a factor of ten is about three and a third bits; a one-in-a-thousand event is just under ten bits, because 2¹⁰ = 1024 is a hair more than 1000.

The robot rows are the check that the definition is consistent with the warm-up example: each code word's length equals its instruction's information exactly, and the weighted average ½·1 + ¼·2 + ⅛·3 + ⅛·3 = 1.75 bits per instruction is both the code's measured cost and, once the video names it a few minutes later, the entropy of that distribution. To move between units, multiply: 1 bit = ln 2 ≈ 0.6931 nats = log₁₀ 2 ≈ 0.3010 hartleys.

What the definition claims, and what it does not 17:10

Grant is careful here, and it is the most easily skipped half-minute in the chapter. He insists there is real content in the definition — it is not a relabelling of probabilities into a friendlier unit — and then immediately fences off the overclaim. The content is the identity established above: in a perfect scheme, the bits spent on a message equal its information. The fence is that perfect schemes generally do not exist, because real probabilities are not powers of two. So the general statement is a bound, and it is a bound on an average:

expected code length  ≥  Σ p(x)·log₂(1/p(x))     (averaged over all messages)

The averaging qualifier is not a technicality. Any single message can be compressed to almost nothing by a codebook that was built to expect it — a compressor whose output for Moby-Dick is the single bit 1 is easy to write and useless, and it pays for that one short code word by making everything else longer. The bound bites over the ensemble, not over the specimen. (My addition, for the reader who wants the name: what makes the bound unbeatable in the first place is Kraft's inequality on prefix-free codes, which is the algebraic form of P03's “pushing down a bump in the rug” picture; combined with Gibbs' inequality it gives the noiseless coding theorem the video reaches when it defines entropy.)

Where people get stuck

“Why is there a minus sign — is information negative?” No. For 0 < p ≤ 1, log₂ p is already zero or negative, and the minus sign cancels that, so −log₂ p ≥ 0. Written as log₂(1/p) the same number looks obviously non-negative, because 1/p ≥ 1. The two forms are algebraically identical and the choice between them is pure taste; authors who dislike explaining the minus sign write the fraction, authors who want a compact expression write the minus. If you ever compute a negative information content, you have a probability greater than 1 and a bug.

“Information” here has nothing to do with meaning. The formula's only input is p. A string of random hex digits and a line of Shakespeare of the same improbability carry identical information content, and a profound message that everyone expected carries almost none. This is a measure of surprisal — the standard alternative name for −log p, and a more honest one. The corollary worth internalising: information is always relative to a probability model. Change the distribution you are scoring against and every information value changes, which is why the video's letter probabilities from a small local GPT are a model's opinion rather than a fact about English.

“What could 4.19 bits possibly mean? You cannot send a fraction of a bit.” Correct — for a single symbol, under a code that maps symbols to fixed code words. The resolution is that the definition lives at the level of whole messages and long runs. Fractional per-symbol informations sum to a total for the message, and it is that total which a good coder gets close to, spending whole bits only at the very end. (My addition: the technique that actually cashes fractional bits is arithmetic coding, which encodes an entire message as one number in an interval rather than symbol by symbol; the video builds this in Part 3.)

“So a perfect code always exists?” No, and the chapter says so at 17:10. Exact equality between code length and information requires every probability to be a negative power of two. Otherwise you get a lower bound that is approachable but generally not attainable — Huffman coding, for instance, is optimal among symbol-by-symbol codes yet can still overshoot the bound, most painfully when one symbol has probability close to 1 and its information is a small fraction of a bit that Huffman must round up to a whole one.

Going deeper, verified

• A Mathematical Theory of Communication — Claude Shannon (1948) · The source. Section 6 and Appendix 2 contain the uniqueness argument for H; the choice-of-base-as-choice-of-unit discussion is on the first two pages. Linked by Grant in the video description.
• Visual Information Theory — Christopher Olah (2015) · The post Grant credits for the stacked-bar way of drawing entropy; its “cost of a message” pictures are the best visual companion to log(1/p) anywhere online.
• Information Theory, Inference, and Learning Algorithms — David MacKay (2003) · Chapter 2 defines the Shannon information content as h(x) = log₂(1/p(x)) and Chapter 5 gives Kraft's inequality and the symbol-code bound. Free full PDF from the author's site.
• Cauchy's functional equation — · The uniqueness step in this page's axiomatic section, including the pathological non-measurable solutions and the exact list of regularity conditions that rule them out.
• Information content (surprisal) — · Compact reference for the definition, its unit conversions, and its relationship to entropy as an expectation.

Exercises

1. Close the loop on the robot — For the four instructions with probabilities ½, ¼, ⅛, ⅛, compute −log₂ p for each and compare with the code word lengths 1, 2, 3, 3. Then compute the weighted average. A good answer gets 1, 2, 3, 3 bits and 1.75 bits per instruction, and states why the match is exact here but would fail for probabilities like 0.4, 0.3, 0.2, 0.1 — computing that second case's information values and its bound, ≈ 1.846 bits, is the real point of the exercise.
2. Unit conversion by hand — Compute the information of a one-in-a-thousand event in bits, nats, and hartleys. A good answer gives 9.966 bits, 6.908 nats and 3 hartleys, and explains why the hartley figure is exactly 3 while the others are not — which is the whole content of “the base is only a choice of unit”.
3. Do the uniqueness argument properly — Starting only from I(p·q) = I(p) + I(q), prove I(pⁿ) = n·I(p) for positive integers n, then extend to rational exponents m/n, then to all reals. A good answer names precisely the step where the extension from rationals to reals requires an extra hypothesis, states which hypothesis it is using (continuity or monotonicity), and says what goes wrong without one.