Entropy & Information Content

Table of Contents

1. Learning Objectives
2. Prerequisites
3. Notation
4. Core Intuition
5. Information Content of an Event
6. The Uniqueness Theorem for Self-Information
7. Shannon Entropy: Definition and Derivation
8. Properties of Entropy: Proofs
9. Conditional Entropy and the Chain Rule
10. Mutual Information
11. Differential Entropy for Continuous Variables
12. Maximum Entropy Principle
13. Source Coding and the Entropy Lower Bound
14. Connection to Machine Learning
15. Common Pitfalls and Misconceptions
16. Research Perspective
17. Summary of Takeaways
18. Exercises

Learning Objectives

After reading this chapter, you should be able to:

1. State the axioms for self-information and prove that $I(p) = -\log p$ is the unique solution (up to base).
2. Define Shannon entropy and prove non-negativity, the upper bound $H(X) \leq \log n$, and when equality holds.
3. Derive and apply the chain rule for joint entropy and conditional entropy.
4. Define mutual information and prove the identity $I(X; Y) = H(X) - H(X \mid Y)$.
5. Distinguish discrete entropy from differential entropy and explain why differential entropy can be negative.
6. State the maximum entropy principle for discrete and continuous settings.
7. Explain how cross-entropy loss, perplexity, and the information bottleneck arise from entropy concepts.

Prerequisites

• Bayes' Theorem: conditional probability, product rule, conditioning reduces uncertainty.
• Vectors, Spans & Linear Independence: Jensen's inequality (concave $\log$) appears in entropy bounds.

Later connections:

• KL Divergence: entropy difference defines divergence.
• The Multivariate Gaussian: Gaussian achieves maximum differential entropy for fixed variance.

Notation

• $H(X)$ — Shannon entropy (nats or bits)
• $H(X \mid Y)$ — Conditional entropy
• $I(X; Y)$ — Mutual information
• $p(x), p(x, y)$ — Mass or density functions
• $\log$ — Natural logarithm unless stated otherwise

Core Intuition

How much information does a random event carry? A fair coin flip ($p = 1/2$) is more informative than a biased coin ($p = 0.99$) because the outcome is more uncertain. Shannon's insight (1948) was to quantify this intuition axiomatically: information should be non-negative, zero for certain events, and additive for independent events. The unique measure is $I(p) = -\log p$.

The entropy $H(X) = \mathbb{E}[-\log p(X)]$ is the average information content — the expected surprise when sampling from $X$. It answers: How many bits (on average) are needed to encode outcomes of $X$ using an optimal code?

In machine learning, entropy is everywhere:

• Cross-entropy loss measures how many extra bits our model uses compared to the true distribution.
• Perplexity exponentiates cross-entropy to give an effective "branching factor" for language models.
• Mutual information quantifies how much a representation tells us about the target — the foundation of the information bottleneck.

Series context. This is Part III of Chapter 3 in Volume I. It precedes KL Divergence, where $D_{\text{KL}}(p \| q) = H(p, q) - H(p)$.

Information Content of an Event

Definition 1 (Self-Information). The information content (self-information, surprisal) of an event with probability $p \in (0, 1]$ is:

where $b$ is the log base. We use $b = 2$ for bits and $b = e$ for nats ($1 \text{ bit} = \ln 2 \text{ nats}$).

Example 1. For a fair die outcome ($p = 1/6$): $I(1/6) = \log_2 6 \approx 2.585$ bits. For a certain event ($p = 1$): $I(1) = 0$ bits.

Axioms for Self-Information. A function $I: (0, 1] \to \mathbb{R}_{\geq 0}$ should satisfy:

1. Non-negativity: $I(p) \geq 0$.
2. Zero for certainty: $I(1) = 0$.
3. Continuity: $I$ is continuous on $(0, 1]$.
4. Additivity for independence: $I(p_1 p_2) = I(p_1) + I(p_2)$ when two events with probabilities $p_1, p_2$ are independent (joint probability $p_1 p_2$).

Interpretation of (4). Learning that two independent events occurred should convey the sum of their individual information contents — information is additive for independent surprises.

The Uniqueness Theorem for Self-Information

Theorem 1 (Uniqueness of Self-Information). The only function $I: (0, 1] \to \mathbb{R}_{\geq 0}$ satisfying axioms 1–4 is $I(p) = -c \log p$ for some constant $c > 0$.

Proof. Axiom 4 states $I(p_1 p_2) = I(p_1) + I(p_2)$. Define $f(p) = I(p)$ for $p \in (0, 1]$. This is Cauchy's functional equation on the multiplicative group $(\mathbb{R}_{>0}, \times)$.

Step 1 — Reduction to additive form. Let $g(x) = f(e^{-x})$ for $x \geq 0$. Then for $x, y \geq 0$:

So $g$ satisfies the additive Cauchy equation on $[0, \infty)$.

Step 2 — Continuity implies linearity. By axiom 3, $f$ is continuous, hence $g$ is continuous. The only continuous solution to $g(x+y) = g(x) + g(y)$ on $[0, \infty)$ is $g(x) = cx$ for some $c \geq 0$.

Step 3 — Back-substitution. $f(p) = g(-\log p) = -c \log p$. Non-negativity (axiom 1) and monotonicity (axiom 2: $I(1) = 0$, and $I$ decreases as $p$ increases) require $c > 0$. $\blacksquare$

Remark. The choice of base $b$ is conventional: $I(p) = -\log_2 p$ gives bits; $I(p) = -\ln p$ gives nats. All bases differ by a constant factor $\log_b e$.

Shannon Entropy: Definition and Derivation

Definition 2 (Shannon Entropy — Discrete). For discrete random variable $X$ with PMF $p(x) = P(X = x)$:

Convention. Define $0 \log 0 = \lim_{p \to 0^+} p \log p = 0$, ensuring events with zero probability contribute nothing.

Definition 3 (Joint and Conditional Entropy). For joint PMF $p(x, y)$:

Example 2 (Binary Entropy). For $X \sim \text{Bernoulli}(p)$:

This is symmetric about $p = 1/2$, where $H_b(1/2) = 1$ bit (maximum). At $p \in \{0, 1\}$, $H = 0$.

Example 3 (Uniform Distribution). For $X$ uniform on $\{1, \ldots, n\}$: $H(X) = \log n$ bits.

Properties of Entropy: Proofs

Property 1 (Non-Negativity). $H(X) \geq 0$, with equality iff $X$ is deterministic (supported on a single value).

Proof. Each term $-p(x) \log p(x) \geq 0$ since $p(x) \in [0, 1]$ implies $\log p(x) \leq 0$. Equality requires $p(x) \in \{0, 1\}$ for all $x$, with exactly one $p(x) = 1$. $\blacksquare$

Property 2 (Upper Bound). For $X$ taking at most $n$ distinct values:

with equality iff $X$ is uniform on $n$ values.

Proof. By Jensen's inequality, since $-\log$ is convex (equivalently, $\log$ is concave):

Equality in Jensen holds iff $1/p(X)$ is constant a.e., i.e., $p(x) = 1/n$ for all $x$ in the support. $\blacksquare$

Property 3 (Invariance under bijection). If $Y = g(X)$ for a bijection $g$, then $H(Y) = H(X)$.

Proof. $p_Y(y) = p_X(g^{-1}(y))$, and the sum (3) is unchanged under relabeling. $\blacksquare$

Property 4 (Concavity in the distribution). $H(X)$ is concave in the probability vector $(p(x_1), \ldots, p(x_n))$.

This implies that mixing distributions increases entropy — uncertainty is maximized at the "center" of the probability simplex.

Conditional Entropy and the Chain Rule

Theorem 2 (Chain Rule for Entropy). For any random variables $X$ and $Y$:

Proof. Using $p(x,y) = p(x) p(y \mid x)$:

Splitting the sum:

The first term is $H(Y \mid X)$. For the second: $\sum_y p(x,y) = p(x)$, so $-\sum_{x,y} p(x,y) \log p(x) = -\sum_x p(x) \log p(x) = H(X)$. $\blacksquare$

Theorem 3 (Conditioning Reduces Entropy). $H(Y \mid X) \leq H(Y)$, with equality iff $X$ and $Y$ are independent.

Proof. From (9): $H(Y) = H(X, Y) - H(X \mid Y)$ and $H(Y \mid X) = H(X, Y) - H(X)$. Alternatively, directly:

since $\log \frac{p(x,y)}{p(x)p(y)} \geq 0$ iff $p(x,y) \geq p(x)p(y)$ — the log-sum inequality gives non-negativity. Equality when $p(x,y) = p(x)p(y)$ everywhere. $\blacksquare$

Interpretation. Observing $X$ cannot increase average uncertainty about $Y$. Side information helps (or at least does not hurt) prediction.

Corollary 1 (General Chain Rule). For $X_1, \ldots, X_n$:

This decomposition is fundamental to sequential coding and autoregressive language models.

Mutual Information

Definition 4 (Mutual Information). The mutual information between $X$ and $Y$ is:

Theorem 4. $I(X; Y) \geq 0$, with equality iff $X$ and $Y$ are independent.

Proof. From (12), $H(Y) - H(Y \mid X) \geq 0$. $\blacksquare$

Interpretation. $I(X; Y)$ measures how much knowing $Y$ reduces uncertainty about $X$ (equivalently, how much knowing $X$ reduces uncertainty about $Y$). It is symmetric: $I(X; Y) = I(Y; X)$.

Definition 5 (KL Connection — Preview).

the KL divergence between the joint distribution and the product of marginals. Developed fully in KL Divergence.

Differential Entropy for Continuous Variables

Definition 6 (Differential Entropy). For continuous $X$ with PDF $f(x)$:

Key differences from discrete entropy:

1. Can be negative. Example: $X \sim \text{Uniform}(0, 1/2)$ has $h(X) = -\int_0^{1/2} 2 \log 2\, dx = -\log 2 < 0$.
2. Not invariant to coordinate changes. Under $Y = g(X)$, $h(Y) = h(X) + \mathbb{E}[\log |g'(X)|]$.
3. Not a direct coding bound (unlike discrete $H$), but differences of differential entropies are meaningful.

Theorem 5 (Gaussian Maximum Entropy — Univariate). For fixed variance $\sigma^2$, the Gaussian $\mathcal{N}(\mu, \sigma^2)$ maximizes $h(X)$:

with equality iff $X \sim \mathcal{N}(\mu, \sigma^2)$.

Proof sketch. Lagrange multipliers on $h(f) = -\int f \log f$ subject to $\int f = 1$ and $\int (x-\mu)^2 f = \sigma^2$. The optimizer satisfies $\log f(x) = -1 - \lambda_0 - \lambda_1(x-\mu)^2$, i.e., $f$ is Gaussian. $\blacksquare$

Multivariate extension: see The Multivariate Gaussian, Theorem 9.

Maximum Entropy Principle

Principle (Maximum Entropy). Given constraints (e.g., known mean, variance, support), choose the distribution that maximizes entropy subject to those constraints. This is the least informative (most agnostic) distribution consistent with what is known.

Theorem 6 (Discrete Maximum Entropy). Among distributions on $n$ points with no further constraints, the uniform distribution maximizes $H(X)$ at $\log n$.

Theorem 7 (Continuous — Fixed Mean and Variance). Among distributions on $\mathbb{R}$ with given mean $\mu$ and variance $\sigma^2$, the Gaussian maximizes $h(X)$.

Theorem 8 (Exponential Family). Maximum entropy subject to constraints $\mathbb{E}[T_k(X)] = t_k$ for sufficient statistics $T_k$ yields an exponential family distribution:

ML significance. Logistic regression arises from max-entropy with fixed mean constraints on features; Gaussian noise models arise from max-entropy with fixed variance. Prior selection in Bayes' Theorem often uses max-entropy reasoning.

Source Coding and the Entropy Lower Bound

Theorem 9 (Shannon's Source Coding Theorem — Informal). The expected code length for any lossless encoding of i.i.d. samples from $p$ is bounded below by $H(X)$ bits per symbol. There exist codes (e.g., Huffman, arithmetic) achieving $H(X) + o(1)$.

Proof sketch (lower bound). For code lengths $\ell(x)$ with Kraft inequality $\sum_x 2^{-\ell(x)} \leq 1$, define $q(x) = 2^{-\ell(x)} / Z$. Then:

since $D_{\text{KL}}(p \| q) \geq 0$. $\blacksquare$

Interpretation. Entropy is the fundamental limit of compression. Language models that achieve low cross-entropy are approaching the entropy of natural language — the irreducible randomness in text.

Connection to Machine Learning

Cross-Entropy Loss

For true distribution $p$ and model $q$:

Since $H(p)$ is constant w.r.t. model parameters, minimizing cross-entropy $\equiv$ minimizing KL divergence $\equiv$ Maximum Likelihood Estimation.

For one-hot labels $p = \delta_{y}$ and softmax output $q$:

the standard classification loss.

Perplexity

For language models:

Perplexity $k$ means the model assigns on average the same probability as choosing uniformly among $k$ options. GPT-class models achieve perplexity $\sim 10$–$30$ on diverse corpora; the entropy of English text is estimated at $\sim 1.0$–$1.5$ bits per character.

Information Bottleneck

Find representation $T$ of input $X$ that maximizes $I(T; Y)$ (relevant to target $Y$) while minimizing $I(X; T)$ (compression):

This provides a theoretical framework for understanding what deep networks extract — task-relevant information at minimal complexity.

Decision Trees and Information Gain

Splitting a node on feature $X_j$ maximizes information gain $I(Y; X_j) = H(Y) - H(Y \mid X_j)$ — the reduction in label entropy. ID3 and C4.5 use this criterion.

Common Pitfalls and Misconceptions

Pitfall 1: Treating differential entropy like discrete entropy. Negative differential entropy does not mean "negative information." Only differences (e.g., KL divergence) are invariant and interpretable in the continuous case.

Pitfall 2: Confusing entropy with variance. High variance does not always mean high entropy (e.g., a deterministic function of a high-entropy variable can have low entropy). Entropy depends on the full distribution, not just second moments.

Pitfall 3: Assuming $H(Y \mid X) = 0$ means $Y$ is a function of $X$. It means $Y$ is determined given $X$, but $Y$ could still be random if $X$ is unobserved.

Pitfall 4: Ignoring the base of the logarithm. Entropy in bits vs nats differs by $\ln 2$. Cross-entropy loss in deep learning typically uses nats ($\ln$); perplexity uses bits ($\log_2$).

Pitfall 5: Equating low training cross-entropy with good generalization. $H(p, q)$ on training data can be minimized while $H(p_{\text{test}}, q)$ remains high — overfitting. See Bias–Variance Tradeoff.

Research Perspective

Claude Shannon's "A Mathematical Theory of Communication" (1948) established entropy, channel capacity, and source coding — founding information theory. Jaynes (1957) extended maximum entropy to statistical mechanics and Bayesian inference. The connection to ML emerged gradually: cross-entropy as classification loss (Bridle, 1990), the information bottleneck (Tishby et al., 1999), and modern use in language modeling evaluation.

Current research uses mutual information for representation learning (MINE, InfoNCE), studies entropy of neural network outputs for calibration, and applies information-theoretic bounds to generalization. The entropy of LLM-generated text and its relationship to human text entropy is an active measurement problem.

Summary of Takeaways

• Self-information — $I(p) = -\log p$ — Per-sample surprisal
• Entropy — $H(X) = -\sum p \log p$ — Average uncertainty
• Conditional entropy — $H(Y \mid X) = H(X,Y) - H(X)$ — Remaining uncertainty
• Chain rule — $H(X,Y) = H(X) + H(Y \mid X)$ — Autoregressive decomposition
• Mutual information — $I(X;Y) = H(X) - H(X \mid Y)$ — Feature relevance
• Cross-entropy — $H(p,q) = -\sum p \log q$ — Classification loss
• Perplexity — $2^{H(p,q)}$ — LM evaluation
• Max entropy — Uniform (discrete), Gaussian (continuous) — Prior / noise selection

Next article: KL Divergence → — measuring discrepancy between distributions.

Exercises

Exercise 1 (Uniqueness). Verify that $I(p) = -\log_2 p$ satisfies all four axioms for self-information.

Exercise 2 (Binary entropy). Plot $H_b(p)$ and prove it is maximized at $p = 1/2$ by differentiation.

Exercise 3 (Chain rule). Prove (13) by induction on $n$.

Exercise 4 (Mutual information). Show $I(X; Y) = D_{\text{KL}}(p(x,y) \| p(x)p(y))$ using definitions.

Exercise 5 (Differential entropy). Compute $h(X)$ for $X \sim \text{Uniform}(a, b)$ and verify (17) at equality when $b - a = \sqrt{12}\sigma$.

Exercise 6 (Coding). For $X \sim \{A, B, C\}$ with $p = (1/2, 1/4, 1/4)$, construct a prefix code and compare its expected length to $H(X)$.

Exercise 7 (Conceptual). Why does minimizing cross-entropy not guarantee good test performance?

Exercise 8 (Proof). Complete the proof of Theorem 3 (conditioning reduces entropy) using the log-sum inequality.