Information Theory: Entropy and Mutual Information

⚡ Key Takeaways

One-line statement: Entropy $H(X)$ measures the average uncertainty (in bits) of a random variable, while mutual information $I(X;Y)$ measures how much knowing one variable reduces uncertainty about another. Key result in words: A source with entropy $H$ bits per symbol cannot be losslessly compressed below $H$ bits/symbol on average; the maximum reliable communication rate over a noisy channel equals the channel's maximal mutual information. Where it applies: Data compression, communication theory, cryptography, machine learning, statistics, neuroscience, and statistical physics. Who/when: Claude E. Shannon, A Mathematical Theory of Communication (1948).

💡 The Core Insight

Information equals surprise. A certain event (probability 1) carries zero information; a rare event carries much. The right measure of the surprise of an event with probability $p$ is $-\log p$ , because surprise should be additive for independent events and decreasing in probability. Entropy is the expected surprise, and every other quantity — joint entropy, conditional entropy, mutual information, relative entropy — is built from this single primitive.

DefinitionSelf-Information (Surprisal)

For an event with probability $p$ , the self-information or surprisal is

1

\quad I(x) = -\log_b p(x) = \log_b \frac{1}{p(x)}

Derivation hint: Demand a measure $I(p)$ that is continuous, decreasing in $p$ , and additive over independent events ( $I(p_1 p_2) = I(p_1) + I(p_2)$ ); the only solutions are $I(p) = -c\log p$ . The base $b$ fixes the unit: $b=2$ gives bits (shannons), $b=e$ gives nats, $b=10$ gives hartleys (dits). We use base 2 throughout unless noted.

DefinitionShannon Entropy

For a discrete random variable $X$ with alphabet $\mathcal{X}$ and probability mass function $p(x)=\Pr(X=x)$ , the entropy is

2

\quad H(X) = -\sum_{x\in\mathcal{X}} p(x)\log_2 p(x) = \mathbb{E}\!\left[\log_2 \frac{1}{p(X)}\right]

Derivation hint: Take the expectation of the self-information $[1]$ over the distribution of $X$ ; adopt the convention $0\log 0 = 0$ (justified by $\lim_{p\to 0^+} p\log p = 0$ ).

Symbols: $X$ = random variable; $\mathcal{X}$ = its (finite or countable) alphabet; $p(x)$ = pmf; $H(X)$ = entropy in bits. Entropy depends only on the distribution $\{p(x)\}$ , not on the values of $X$ .

DefinitionJoint and Conditional Entropy

For two random variables $X,Y$ with joint pmf $p(x,y)$ :

3

\quad H(X,Y) = -\sum_{x,y} p(x,y)\log_2 p(x,y)

Derivation hint: Apply $[2]$ to the pair $(X,Y)$ treated as a single random variable over $\mathcal{X}\times\mathcal{Y}$ .

4

\quad H(Y\mid X) = -\sum_{x,y} p(x,y)\log_2 p(y\mid x) = \sum_x p(x)\,H(Y\mid X=x)

Derivation hint: Average the entropy of $Y$ within each slice $X=x$ , weighting by $p(x)$ ; use $p(x,y)=p(x)p(y\mid x)$ .

TheoremChain Rule for Entropy

5

\quad H(X,Y) = H(X) + H(Y\mid X) = H(Y) + H(X\mid Y)

Derivation hint: Expand $\log p(x,y)=\log p(x)+\log p(y\mid x)$ inside the sum $[3]$ and separate terms. More generally, $H(X_1,\dots,X_n) = \sum_{i=1}^n H(X_i \mid X_1,\dots,X_{i-1})$ .

DefinitionMutual Information

The mutual information between $X$ and $Y$ is

6

\quad I(X;Y) = \sum_{x,y} p(x,y)\log_2 \frac{p(x,y)}{p(x)\,p(y)}

Derivation hint: It is the relative entropy (KL divergence) between the joint distribution $p(x,y)$ and the product of marginals $p(x)p(y)$ — the "distance" from independence. Equivalent forms, all derivable from $[5]$ and $[6]$ :

7

\quad I(X;Y) = H(X) - H(X\mid Y) = H(Y) - H(Y\mid X) = H(X)+H(Y)-H(X,Y)

Derivation hint: Substitute $p(x,y)=p(x\mid y)p(y)$ in $[6]$ , split the logarithm, and recognize $H(X)$ and $H(X\mid Y)$ .

DefinitionRelative Entropy (Kullback–Leibler Divergence)

For two pmfs $p,q$ on the same alphabet,

8

\quad D(p\,\|\,q) = \sum_x p(x)\log_2 \frac{p(x)}{q(x)} \geq 0

Derivation hint: Nonnegativity follows from Jensen's inequality applied to the convex function $-\log$ ; equality holds iff $p=q$ . This is <strong>Gibbs' inequality</strong>. Mutual information is the special case $I(X;Y) = D\big(p(x,y)\,\|\,p(x)p(y)\big)$ .

ProofMutual Information is Nonnegative and Symmetric

We show $I(X;Y)\geq 0$ with equality iff $X\perp Y$ .

Step 1. By definition $[6]$ , $I(X;Y) = D\big(p(x,y)\,\|\,p(x)p(y)\big)$ , a KL divergence.

Step 2. Write $-I(X;Y) = \sum_{x,y} p(x,y)\log_2\frac{p(x)p(y)}{p(x,y)}$ .

Step 3. Apply Jensen's inequality to the concave function $\log$ (expectation moves inside):

-I(X;Y) \leq \log_2 \sum_{x,y} p(x,y)\cdot\frac{p(x)p(y)}{p(x,y)} = \log_2 \sum_{x,y} p(x)p(y) = \log_2 1 = 0.

Step 4. Hence $I(X;Y)\geq 0$ . Equality in Jensen requires the argument constant: $\frac{p(x)p(y)}{p(x,y)}=1$ , i.e. $p(x,y)=p(x)p(y)$ — independence.

Step 5. Symmetry $I(X;Y)=I(Y;X)$ is immediate because $[6]$ treats $x,y$ interchangeably.

Corollary (conditioning reduces entropy). From $[7]$ , $H(X\mid Y) = H(X) - I(X;Y) \leq H(X)$ . Knowing $Y$ never increases uncertainty on average (it may increase it for a particular value $Y=y$ ). $\blacksquare$

∎

TheoremBounds on Entropy

For a variable on an alphabet of size $m=|\mathcal{X}|$ ,

9

\quad 0 \leq H(X) \leq \log_2 m

Derivation hint: Left bound: each term $-p\log p \geq 0$ . Right bound: $H(X) - \log_2 m = -D\big(p\,\|\,\text{uniform}\big) \leq 0$ by $[8]$ . $H(X)=0$ iff $X$ is deterministic; $H(X)=\log_2 m$ iff $X$ is uniform.

Figure

Binary entropy function

H(p) = -p\log_2 p - (1-p)\log_2(1-p)

CE

Claude Elwood Shannon

1916–2001

An American mathematician and electrical engineer at Bell Labs, Shannon single-handedly founded information theory with his 1948 paper. He chose the name "entropy" on the suggestion of John von Neumann, who reputedly told him: "No one knows what entropy really is, so in a debate you will always have the advantage." The mathematical form of Shannon entropy is identical to the Gibbs entropy of statistical mechanics, a coincidence Shannon exploited deliberately. Beyond information theory, Shannon contributed to cryptography (proving the one-time pad's perfect secrecy), digital circuit design (his master's thesis applied Boolean algebra to switching), and built whimsical machines including a maze-solving mechanical mouse and a juggling robot.

🧠 Intuition

Think of entropy as the average number of yes/no questions in an optimal guessing game. If a horse race has 8 equally likely winners, you need $\log_2 8 = 3$ questions ("Is it in the first half?" etc.), so $H = 3$ bits. But if one horse wins half the time and others are rare, a smart questioner asks "Is it the favorite?" first — most games end in one question, and the average number of questions drops below 3. That average is exactly the entropy. Mutual information is how much a hint helps. Suppose you must guess $X$ , but a friend whispers a related variable $Y$ . The reduction in your expected number of questions — from $H(X)$ down to $H(X\mid Y)$ — is $I(X;Y)$ . If $Y$ tells you everything, $I(X;Y)=H(X)$ ; if $Y$ is irrelevant, $I(X;Y)=0$ .

🧠 Intuition

The Venn diagram picture. Draw two overlapping circles for $H(X)$ and $H(Y)$ . The overlap is $I(X;Y)$ ; the union is $H(X,Y)$ ; the left crescent is $H(X\mid Y)$ ; the right crescent is $H(Y\mid X)$ . Every identity in $[5]$ and $[7]$ becomes obvious set arithmetic. Caution: this picture works beautifully for two variables but breaks for three or more, where "triple intersections" $I(X;Y;Z)$ can be negative and have no set-theoretic meaning.

ExampleEntropy of a Biased Coin

Given: A coin with $\Pr(\text{heads})=0.9$ , $\Pr(\text{tails})=0.1$ .

Find: The entropy $H(X)$ .

Steps:

H(X) = -0.9\log_2 0.9 - 0.1\log_2 0.1.

Compute $\log_2 0.9 = -0.152$ , so $-0.9(-0.152) = 0.137$ . Compute $\log_2 0.1 = -3.322$ , so $-0.1(-3.322) = 0.332$ . Sum: $0.137 + 0.332 = 0.469$ .

\boxed{H(X) \approx 0.469 \text{ bits}}

Interpretation: Far below the maximum of 1 bit (fair coin). On average, 1000 flips of this coin carry only ~469 bits of information and could be compressed to ~469 bits.

ExampleMutual Information of a Binary Symmetric Channel

Given: Send $X\in\{0,1\}$ uniformly ( $\Pr=0.5$ each) through a channel that flips the bit with probability $f=0.1$ . Output is $Y$ .

Find: $I(X;Y)$ .

Steps: By symmetry, $Y$ is also uniform: $\Pr(Y=0)=\Pr(Y=1)=0.5$ , so $H(Y)=1$ bit. The noise is independent of the input, so the conditional entropy is the entropy of the flip:

H(Y\mid X) = H(f) = -0.1\log_2 0.1 - 0.9\log_2 0.9 = 0.469 \text{ bits}.

Apply form $[7]$ :

I(X;Y) = H(Y) - H(Y\mid X) = 1 - 0.469 = 0.531.

\boxed{I(X;Y) \approx 0.531 \text{ bits per channel use}}

Interpretation: This equals the channel capacity of the BSC at $f=0.1$ . Each transmission reliably conveys about 0.53 bits despite carrying 1 raw bit — the 10% noise costs nearly half the channel.

⚠️ Common mistake

Conditioning reduces entropy only on average. The inequality $H(X\mid Y)\leq H(X)$ holds for the average conditional entropy $[4]$ . For a specific outcome $Y=y$ , it is entirely possible that $H(X\mid Y=y) > H(X)$ — a particular observation can leave you more confused than before. Only the weighted average is guaranteed to drop.

⚠️ Common mistake

Entropy is not "the amount of disorder you can see." $H(X)$ depends only on the probability distribution, not on the meaning, structure, or perceptual disorder of outcomes. A perfectly ordered-looking deterministic sequence has zero entropy; a uniformly random sequence has maximal entropy. The famous text "to be or not to be" and a random scramble of the same letters can have very different entropies depending only on the assumed source distribution.

CounterexampleMutual information is not transitive

One might guess that if $X$ shares information with $Y$ , and $Y$ shares information with $Z$ , then $X$ and $Z$ must share information. False. Let $X,Y$ be independent fair bits and define $Z = X \oplus Y$ (XOR). Then:

$I(X;Z)=0$ and $I(Y;Z)=0$ : each of $X,Y$ alone is independent of $Z$ (knowing only $X$ tells you nothing about the XOR, since $Y$ is still random).
Yet $I(X,Y;Z) = 1$ bit: the pair fully determines $Z$ .

Information can hide in joint structure invisible to any single variable, contradicting naive transitivity intuitions.

connection

Mutual information is the bridge between Probability Theory and communication. The KL divergence $[8]$ underlies hypothesis testing and the Maximum Likelihood Estimation framework, where minimizing $D(p_{\text{data}}\|p_\theta)$ equals maximizing likelihood. In machine learning, the cross-entropy loss $-\sum p\log q$ used to train classifiers equals $H(p) + D(p\|q)$ , so minimizing it minimizes the KL divergence to the true labels. Entropy connects directly to Statistical Mechanics: Shannon's $H$ equals the Gibbs–Boltzmann entropy $S/k_B\ln 2$ , and the maximum entropy principle derives equilibrium distributions (e.g. the Boltzmann distribution) as the least-biased choice given known constraints. Mutual information also generalizes Correlation and Covariance: unlike correlation, $I(X;Y)$ captures all dependence, including nonlinear, and is zero iff variables are truly independent.

🔬 Where this appears

⏳ History

- 1850s–1870s — Rudolf Clausius and Ludwig Boltzmann develop thermodynamic and statistical entropy; Boltzmann's

S=k\log W

foreshadows Shannon's formula.

- 1928 — Ralph Hartley (Bell Labs) proposes

\log m

as a measure of information for

m

equally likely messages, anticipating the uniform-case entropy.

- 1948 — Claude Shannon publishes A Mathematical Theory of Communication in the Bell System Technical Journal, defining entropy, mutual information, channel capacity, and proving the source and channel coding theorems.

- 1949 — Shannon's Communication Theory of Secrecy Systems establishes information-theoretic cryptography and perfect secrecy.

- 1951 — Solomon Kullback and Richard Leibler introduce relative entropy (KL divergence), unifying it with statistical inference.

- 1957 — E. T. Jaynes formulates the maximum entropy principle, recasting statistical mechanics as inference and influencing Bayesian statistics.

- 1959 — Shannon proves the rate–distortion theorem, extending the theory to lossy compression.

- 1961 — Rolf Landauer establishes Landauer's principle: erasing one bit dissipates at least

k_BT\ln 2

of heat, physically grounding information.

- 1991 — Thomas Cover and Joy Thomas publish Elements of Information Theory, the canonical modern textbook.

open-problem

Continuous and infinite alphabets. For continuous variables, the differential entropy $h(X)=-\int f(x)\log f(x)\,dx$ replaces $[2]$ , but it is not a true measure of information: it can be negative, is not invariant under coordinate changes, and depends on units. Mutual information, by contrast, remains well-defined and nonnegative in the continuous case, which is why $I(X;Y)$ is the robust fundamental object.

Estimation from data. Entropy and mutual information must usually be estimated from finite samples, and naive plug-in estimators are systematically biased downward; debiasing high-dimensional mutual information remains an active research area (e.g. MINE and neural estimators).

Multivariate information. Decomposing the information that several sources jointly provide about a target into "unique," "redundant," and "synergistic" parts — the partial information decomposition problem — has no universally accepted definition and is an open question in information theory.

Information Theory: Entropy and Mutual Information

Formal Statement

Why It Holds / Derivation

Building Intuition

Worked Examples

Common Misconceptions

Connections

Real-World Applications

Historical Development

Subtleties & Limits

See Also