Information Theory: Entropy and Mutual Information

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).

Information theory quantifies information using probability. Shannon entropy $H (X) = - \sum_{x} p (x) lo g p (x)$ assigns to each random variable a number — measured in bits when the logarithm is base 2 — equal to the average number of yes/no questions needed to determine its value optimally. Mutual information $I (X; Y)$ measures the statistical dependence between two variables: the reduction in uncertainty about $X$ achieved by observing $Y$ . These quantities matter because they set absolute, unbeatable limits on compression and communication that no engineering cleverness can surpass. The surprising fact: information content depends only on the probability distribution, not on the meaning or physical form of the data — and a perfectly random source of $n$ bits is genuinely incompressible.

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 $- lo g 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.

Formal Statement

Self-Information (Surprisal)

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

I (x) = - lo g_{b} p (x) = lo g_{b} \frac{1}{p ( x )}

⟳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 lo g 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.

Shannon Entropy

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

H (X) = - x \in X \sum p (x) lo g_{2} p (x) = E [lo g_{2} \frac{1}{p ( X )}]

⟳Take the expectation of the self-information

[1]

over the distribution of

X

; adopt the convention

0 lo g 0 = 0

(justified by

lim_{p \to 0^{+}} p lo g p = 0

Symbols:

X

= random variable;

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

Joint and Conditional Entropy

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

H (X, Y) = - x, y \sum p (x, y) lo g_{2} p (x, y)

⟳Apply

[2]

to the pair

(X, Y)

treated as a single random variable over

X \times Y

H (Y ∣ X) = - x, y \sum p (x, y) lo g_{2} p (y ∣ x) = x \sum p (x) H (Y ∣ X = x)

⟳Average the entropy of

Y

within each slice

X = x

, weighting by

p (x)

; use

p (x, y) = p (x) p (y ∣ x)

Chain Rule for Entropy

H (X, Y) = H (X) + H (Y ∣ X) = H (Y) + H (X ∣ Y)

⟳Expand

lo g p (x, y) = lo g p (x) + lo g p (y ∣ x)

inside the sum

[3]

and separate terms.

More generally, $H (X_{1}, \dots, X_{n}) = \sum_{i = 1}^{n} H (X_{i} ∣ X_{1}, \dots, X_{i - 1})$ .

Mutual Information

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

I (X; Y) = x, y \sum p (x, y) lo g_{2} \frac{p ( x , y )}{p ( x ) p ( y )}

⟳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]$ :

I (X; Y) = H (X) - H (X ∣ Y) = H (Y) - H (Y ∣ X) = H (X) + H (Y) - H (X, Y)

⟳Substitute

p (x, y) = p (x ∣ y) p (y)

[6]

, split the logarithm, and recognize

H (X)

and

H (X ∣ Y)

Relative Entropy (Kullback–Leibler Divergence)

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

D (p ∥ q) = x \sum p (x) lo g_{2} \frac{p ( x )}{q ( x )} \geq 0

⟳Nonnegativity follows from Jensen's inequality applied to the convex function

- lo g

; equality holds iff

p = q

. This is

Gibbs' inequality.

Mutual information is the special case $I (X; Y) = D (p (x, y) ∥ p (x) p (y))$ .

Why It Holds / Derivation

Mutual Information is Nonnegative and Symmetric

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

Step 1. By definition

[6]

I (X; Y) = D (p (x, y) ∥ p (x) p (y))

, a KL divergence. Step 2. Write

- I (X; Y) = \sum_{x, y} p (x, y) lo g_{2} \frac{p ( x ) p ( y )}{p ( x , y )}

. Step 3. Apply Jensen's inequality to the concave function

lo g

(expectation moves inside):

- I (X; Y) \leq lo g_{2} x, y \sum p (x, y) \cdot \frac{p ( x ) p ( y )}{p ( x , y )} = lo g_{2} x, y \sum p (x) p (y) = lo g_{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 ∣ 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

■

Bounds on Entropy

For a variable on an alphabet of size $m = ∣ X ∣$ ,

0 \leq H (X) \leq lo g_{2} m

⟳Left bound: each term

- p lo g p \geq 0

. Right bound:

H (X) - lo g_{2} m = - D (p ∥ uniform) \leq 0

[8]

H (X) = 0

iff

X

is deterministic;

H (X) = lo g_{2} m

iff

X

is uniform.

Binary entropy function $H(p) = -p\log_2 p - (1-p)\log_2(1-p)$

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.

Building 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 $lo g_{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 ∣ Y)$ — is $I (X; Y)$ . If $Y$ tells you everything, $I (X; Y) = H (X)$ ; if $Y$ is irrelevant, $I (X; Y) = 0$ .

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 ∣ Y)

; the right crescent is

H (Y ∣ 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.

Worked Examples

Entropy of a Biased Coin

Given: A coin with

Pr (heads) = 0.9

Pr (tails) = 0.1

. Find: The entropy

H (X)

. Steps:

H (X) = - 0.9 lo g_{2} 0.9 - 0.1 lo g_{2} 0.1.

Compute

lo g_{2} 0.9 = - 0.152

, so

- 0.9 (- 0.152) = 0.137

. Compute

lo g_{2} 0.1 = - 3.322

, so

- 0.1 (- 3.322) = 0.332

. Sum:

0.137 + 0.332 = 0.469

H (X) \approx 0.469 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.

Mutual 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 ∣ X) = H (f) = - 0.1 lo g_{2} 0.1 - 0.9 lo g_{2} 0.9 = 0.469 bits .

Apply form

[7]

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

I (X; Y) \approx 0.531 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 Misconceptions

Conditioning reduces entropy only on average. The inequality

H (X ∣ Y) \leq H (X)

holds for the average conditional entropy

[4]

. For a specific outcome

Y = y

, it is entirely possible that

H (X ∣ Y = y) > H (X)

— a particular observation can leave you more confused than before. Only the weighted average is guaranteed to drop. 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.

Mutual 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.

Connections

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_{data} ∥ p_{θ})$ equals maximizing likelihood. In machine learning, the cross-entropy loss $- \sum p lo g 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.

Real-World Applications

Lossless data compression — Huffman coding, arithmetic coding, and the formats ZIP, PNG, and FLAC approach the entropy bound $[2]$ ; no scheme beats $H$ bits/symbol on average (Shannon's source coding theorem).
Reliable communication — The channel capacity $C = max_{p (x)} I (X; Y)$ sets the maximum error-free data rate; modern LDPC and turbo codes used in 5G, Wi-Fi, and deep-space probes operate within a fraction of a dB of this Shannon limit.
Cryptography — Shannon's notion of perfect secrecy requires the key entropy to equal the message entropy, proving the one-time pad unbreakable and bounding all ciphers.
Machine learning — Decision trees split on the feature maximizing information gain (mutual information); cross-entropy is the standard loss for classification and language models.
Neuroscience — Mutual information quantifies how much a neuron's spike train tells you about a stimulus, measuring the efficiency of neural coding.
Genomics & bioinformatics — Mutual information detects co-evolving residues and gene-regulatory dependencies that linear correlation misses.
Feature selection & medical diagnosis — Tests and biomarkers are ranked by the mutual information they carry about a disease state.

Historical Development

1850s–1870s — Rudolf Clausius and Ludwig Boltzmann develop thermodynamic and statistical entropy; Boltzmann's $S = k lo g W$ foreshadows Shannon's formula.
1928 — Ralph Hartley (Bell Labs) proposes $lo g 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_{B} T ln 2$ of heat, physically grounding information.
1991 — Thomas Cover and Joy Thomas publish Elements of Information Theory, the canonical modern textbook.

Subtleties & Limits

Continuous and infinite alphabets. For continuous variables, the differential entropy

h (X) = - \int f (x) lo g f (x) d x

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

The Core Insight

Formal Statement

Self-Information (Surprisal)

Shannon Entropy

Joint and Conditional Entropy

Chain Rule for Entropy

Mutual Information

Relative Entropy (Kullback–Leibler Divergence)

Why It Holds / Derivation

Mutual Information is Nonnegative and Symmetric

Bounds on Entropy

Binary entropy function $H(p) = -p\log_2 p - (1-p)\log_2(1-p)$

Claude Elwood Shannon | 1916–2001

Building Intuition

Worked Examples

Entropy of a Biased Coin

Mutual Information of a Binary Symmetric Channel

Common Misconceptions

Mutual information is not transitive

Connections

Real-World Applications

Historical Development

Subtleties & Limits

See Also

Before this

Where this leads