Mutual Information

Why we need it (motivation)

Entropy H(X) tells you how uncertain X is by itself. But many problems are about relationships:

• •Does sensor Y tell us anything about the true state X?
• •Does label Y contain information about feature X?
• •How many bits can a channel input X reliably transmit to output Y?

Correlation is not enough: it’s linear, scale-dependent, and can miss nonlinear dependence. We want a measure that:

1. 1)Works for any (discrete) distributions, not just Gaussian.
2. 2)Is measured in bits (or nats), so it composes with entropy.
3. 3)Has a crisp meaning: reduction in uncertainty.

Mutual information does exactly this.

Definition (core idea)

Let X and Y be discrete random variables with joint distribution p(x,y). The mutual information between X and Y is

I(X;Y) = H(X) − H(X|Y).

Interpretation:

• •H(X) = uncertainty in X before seeing Y.
• •H(X|Y) = remaining uncertainty in X after seeing Y.
• •Their difference is the expected reduction in uncertainty about X gained by observing Y.

Because the definition is symmetric (as we’ll prove), I(X;Y) is also how much X tells you about Y.

Units and log base

If you use log₂, I(X;Y) is in bits. If you use natural log, it’s in nats. The math is identical; only the scale changes.

A concrete mental picture

Think of X as a hidden message and Y as a noisy observation.

• •If Y perfectly determines X, then H(X|Y)=0 ⇒ I(X;Y)=H(X).
• •If Y is unrelated to X, then H(X|Y)=H(X) ⇒ I(X;Y)=0.

So mutual information is a knob between 0 and “all of H(X)” depending on how informative Y is.

Equivalent forms (you should recognize all of these)

We can rewrite I(X;Y) in several equivalent ways:

1) Symmetric conditional-entropy form

I(X;Y) = H(X) − H(X|Y) = H(Y) − H(Y|X).

2) Joint-entropy form

I(X;Y) = H(X) + H(Y) − H(X,Y).

3) Expectation of a log-likelihood ratio

I(X;Y) = ∑ₓ ∑ᵧ p(x,y) log( p(x,y) / (p(x)p(y)) ).

4) KL divergence form

I(X;Y) = D_KL( p(x,y) ‖ p(x)p(y) ).

Each form emphasizes something different:

• •H(X) − H(X|Y): “how much uncertainty is reduced?”
• •H(X)+H(Y)−H(X,Y): “how much overlap between two entropies?”
• •KL form: “how far from independence is the joint distribution?”

A small table of interpretations

Mutual information will become a central “currency” later in channel capacity and information bottleneck.

Why identities matter

Mutual information shows up inside larger derivations (channel capacity, rate–distortion, variational bounds). If you can fluidly switch between its equivalent forms, many proofs become “one line” instead of opaque.

We’ll derive the key identities carefully.

Derivation: I(X;Y) = H(X) + H(Y) − H(X,Y)

Start from the definition:

I(X;Y) = H(X) − H(X|Y).

Use the chain rule for entropy:

H(X,Y) = H(Y) + H(X|Y).

Solve this for H(X|Y):

H(X|Y) = H(X,Y) − H(Y).

Substitute back:

I(X;Y)

= H(X) − (H(X,Y) − H(Y))

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

= H(X) + H(Y) − H(X,Y).

That’s the “overlap” form.

Symmetry: I(X;Y) = H(Y) − H(Y|X)

The overlap form is symmetric in X and Y:

I(X;Y) = H(X) + H(Y) − H(X,Y) = I(Y;X).

So mutual information doesn’t care which variable you call “input” vs “output”.

Interpreting the overlap form

• •H(X)+H(Y) counts uncertainty in each variable separately.
• •H(X,Y) counts uncertainty in the pair together.

If X and Y share some randomness, then the pair is “less uncertain” than the sum, and the difference is the shared part.

This is where the common Venn-diagram intuition comes from. (Be cautious: entropy isn’t literally a set measure, but the algebra matches.)

Bounds you should know

From I(X;Y) = H(X) − H(X|Y):

• •Since conditional entropy is nonnegative, H(X|Y) ≥ 0 ⇒

I(X;Y) ≤ H(X).

Similarly, I(X;Y) ≤ H(Y).

So:

0 ≤ I(X;Y) ≤ min{H(X), H(Y)}.

The upper bound is achievable when one variable is a deterministic function of the other (e.g., Y=f(X) with no collisions). Then knowing one fully determines the other, up to the smaller entropy.

Mutual information as “expected surprise reduction”

Another way to read the definition is pointwise.

Define pointwise mutual information (PMI):

pmi(x,y) = log( p(x,y) / (p(x)p(y)) ).

Then

I(X;Y) = E[ pmi(X,Y) ] = ∑ₓ ∑ᵧ p(x,y) pmi(x,y).

So mutual information is the average log factor by which the joint probability differs from what independence would predict.

• •If (x,y) occurs more often than independence suggests, pmi(x,y) > 0.
• •If it occurs less often, pmi(x,y) < 0.
• •The average across the true joint distribution is always ≥ 0 (we’ll show why next).

A quick intuition check

• •Perfectly informative: If Y=X for a fair bit, then H(X)=1, H(X|Y)=0 ⇒ I=1 bit.
• •Totally uninformative: If Y is an independent coin flip, then H(X|Y)=H(X) ⇒ I=0.

This is the “shared bits” story: mutual information counts how many bits about X are carried by Y, on average.

Why this matters

Two foundational facts make mutual information reliable:

1. 1)Nonnegativity: I(X;Y) ≥ 0 always.
2. 2)Independence criterion: I(X;Y)=0 iff X and Y are independent.

These properties are not obvious from H(X) − H(X|Y) alone, because conditional entropy can behave in unintuitive ways (especially in continuous settings). The cleanest explanation comes from KL divergence.

Derivation: I(X;Y) as KL divergence

Start from the overlap form:

I(X;Y) = H(X) + H(Y) − H(X,Y).

Write each entropy as an expectation:

H(X) = −∑ₓ p(x) log p(x)

H(Y) = −∑ᵧ p(y) log p(y)

H(X,Y) = −∑ₓ∑ᵧ p(x,y) log p(x,y).

Plug in:

I(X;Y)

= −∑ₓ p(x) log p(x) − ∑ᵧ p(y) log p(y) + ∑ₓ∑ᵧ p(x,y) log p(x,y).

Convert the marginal sums into joint sums (since ∑ᵧ p(x,y)=p(x), ∑ₓ p(x,y)=p(y)):

−∑ₓ p(x) log p(x)

= −∑ₓ∑ᵧ p(x,y) log p(x)

−∑ᵧ p(y) log p(y)

= −∑ₓ∑ᵧ p(x,y) log p(y)

So

I(X;Y)

= ∑ₓ∑ᵧ p(x,y) log p(x,y)

− ∑ₓ∑ᵧ p(x,y) log p(x)

− ∑ₓ∑ᵧ p(x,y) log p(y)

Combine logs:

I(X;Y)

= ∑ₓ∑ᵧ p(x,y) log( p(x,y) / (p(x)p(y)) ).

Now recognize this as a KL divergence:

D_KL( p(x,y) ‖ p(x)p(y) )

= ∑ₓ∑ᵧ p(x,y) log( p(x,y) / (p(x)p(y)) ).

Therefore:

I(X;Y) = D_KL( p(x,y) ‖ p(x)p(y) ).

Nonnegativity

KL divergence is always nonnegative:

D_KL(P ‖ Q) ≥ 0,

with equality iff P=Q almost everywhere.

So immediately:

I(X;Y) ≥ 0.

This is a major reason the KL form is beloved: it packages a deep inequality into a known theorem (Gibbs’ inequality).

Independence criterion

Equality holds iff

p(x,y) = p(x)p(y) for all x,y with p(x,y)>0.

But that is exactly the definition of independence. Hence:

I(X;Y) = 0 ⇔ X ⟂ Y.

This gives mutual information a crisp meaning as a dependence measure.

How to interpret the KL view

• •p(x)p(y) is the “best guess” joint distribution if you assume independence.
• •p(x,y) is reality.
• •Mutual information is the penalty (in expected log-loss) for using the independence model when the true data are dependent.

In bits (log₂), it tells you how many extra bits per sample you pay, on average, by pretending the variables are independent.

A dependence measure with nuance

Mutual information detects any dependence, not just linear.

• •If Y = X² and X is symmetric around 0, correlation can be 0, but I(X;Y) > 0.

That makes it especially useful in machine learning for feature selection and representation learning, where dependencies are often nonlinear.

Conditional mutual information (preview)

A closely related quantity you’ll likely meet soon is:

I(X;Y|Z) = H(X|Z) − H(X|Y,Z).

It measures how much X and Y share after accounting for Z. It appears in graphical models and in information bottleneck derivations. You don’t need it yet, but it’s helpful to see that mutual information fits into a larger family of “information differences.”

Why mutual information is a “currency”

In many systems you:

• •compress something (keep fewer bits)
• •but want to preserve relevant information
• •or transmit information through a noisy channel

Mutual information becomes the natural objective/constraint because it counts how many bits about one variable survive into another.

1) Channel capacity (communication)

A channel takes an input X and produces an output Y according to p(y|x). If you choose an input distribution p(x), the channel induces a joint p(x,y)=p(x)p(y|x).

The quantity I(X;Y) measures how much information the output reveals about the input under that choice of p(x).

Shannon capacity is:

C = max_{p(x)} I(X;Y).

Interpretation:

• •You can pick how often you use each input symbol.
• •Different choices yield different amounts of reliably transferable information.
• •Capacity is the best achievable rate (bits per channel use) with vanishing error.

Mutual information is the objective because it precisely measures “how many bits made it through.”

2) Rate–distortion (lossy compression)

Suppose X is a source and you compress it into a representation Ŷ (often written X̂) that is allowed to be imperfect, controlled by a distortion measure d(x, x̂).

Rate–distortion theory studies:

minimize I(X;X̂)

subject to E[d(X,X̂)] ≤ D.

Meaning:

• •I(X;X̂) is the number of bits your compressed representation must retain about X.
• •The constraint controls how much quality you lose.

Again, I(·;·) is the rate.

3) Information bottleneck (learning useful representations)

In supervised learning, you often want a representation T that compresses X but keeps what matters for Y.

The information bottleneck formalizes this tradeoff:

minimize I(X;T) − β I(T;Y).

Interpretation:

• •I(X;T): how much of X is stored in the representation (compression pressure).
• •I(T;Y): how much label-relevant information is preserved (prediction pressure).

This objective is built entirely out of mutual information terms.

4) Feature selection and dependence testing

If you are deciding which feature Xᵢ to keep for predicting Y, a common heuristic is to prefer larger I(Xᵢ;Y). Unlike correlation, this works for arbitrary discrete relationships.

Caution: estimating mutual information from finite data can be tricky (bias, binning choices), but conceptually it’s a powerful criterion.

Summary of where it plugs in

Mutual information is the bridge between probability models and operational goals: how many bits you can transmit, store, or preserve.