Module 5. Mutual information: how much one object tells us about another — exercises and worked solutions · Information Theory for ML

Exercise 1. Nonlinear dependence without correlation

Let $X$ be uniform on $\{-2,-1,1,2\}$ and let $Y=X^2$ .

Compute $\mathbb E[X]$ , $\mathbb E[Y]$ , and $\operatorname{Cov}(X,Y)$ .
Compute $H(Y)$ and $I(X;Y)$ in bits.
Explain why the example does not contradict $I(X;Y)=0\Leftrightarrow X\perp Y$ .

Show answer and solution

Let

X\sim\operatorname{Unif}\{-2,-1,1,2\}, \qquad Y=X^2.

By symmetry,

\mathbb E[X]=0.

Also,

\mathbb E[Y] = \mathbb E[X^2] = \frac{4+1+1+4}{4} = \frac52.

Because $XY=X^3$ ,

\mathbb E[XY] = \mathbb E[X^3] = \frac{-8-1+1+8}{4} = 0.

Therefore,

\operatorname{Cov}(X,Y) = \mathbb E[XY]-\mathbb E[X]\mathbb E[Y] =0.

At the same time, $Y$ takes values $1$ and $4$ with probabilities $1/2$ , so

H(Y)=1\ \text{bit}.

Since $Y$ is a deterministic discrete function of $X$ ,

H(Y\mid X)=0

and

\boxed{I(X;Y)=H(Y)=1\ \text{bit}}.

There is no contradiction. It is the covariance, not MI, that is zero. The variables are clearly dependent: knowing $X$ determines $Y$ . Hence $I(X;Y)>0$ , as expected.

Exercise 2. XOR and failure of univariate feature selection

Let $X_1,X_2\overset{\mathrm{iid}}\sim\operatorname{Bern}(1/2)$ and $Y=X_1\oplus X_2$ .

Show that $I(X_1;Y)=I(X_2;Y)=0$ .
Compute $I((X_1,X_2);Y)$ and $I(X_1;Y\mid X_2)$ .
Explain the failure mode of ranking features by $I(X_i;Y)$ .

Show answer and solution

Let $X_1$ and $X_2$ be independent fair bits and let

Y=X_1\oplus X_2.

Fix $X_1=x_1$ . Since $X_2$ remains a fair bit, $Y=x_1\oplus X_2$ is also uniform on $\{0,1\}$ . Thus the distribution of $Y$ does not depend on the value of $X_1$ :

P(Y=y\mid X_1=x_1)=P(Y=y)=\frac12.

Therefore,

I(X_1;Y)=0.

By symmetry,

I(X_2;Y)=0.

Yet the pair $(X_1,X_2)$ determines $Y$ , and $Y$ is a fair bit. Hence

H(Y)=1\ \text{bit}, \qquad H(Y\mid X_1,X_2)=0,

and

\boxed{I((X_1,X_2);Y)=1\ \text{bit}}.

Once $X_2$ is fixed, $Y$ determines $X_1$ and vice versa. Therefore

H(Y\mid X_2)=1\ \text{bit}, \qquad H(Y\mid X_1,X_2)=0,

and

\boxed{I(X_1;Y\mid X_2)=1\ \text{bit}}.

Individual ranking by $I(X_i;Y)$ assigns zero relevance to both features and may remove them. The failure is the neglect of synergy: information appears only in the feature combination.

Exercise 3. Compressing nuisance without losing target information

Let $Y$ and $N$ be independent fair bits and let the input be $X=(Y,N)$ .

Consider

T_1=X, \qquad T_2=Y, \qquad T_3=Y\oplus E, \quad E\sim\operatorname{Bern}(0.1).

Compute $I(Y;X)$ , $I(Y;T_1)$ , $I(Y;T_2)$ , and $I(Y;T_3)$ .
Which representation removes the nuisance factor without losing target information?
Why should useful compression reduce $I(X;T)$ rather than deliberately reduce $I(Y;T)$ ?

Show answer and solution

We have independent fair bits $Y$ and $N$ , input

X=(Y,N),

and representations

T_1=X, \qquad T_2=Y, \qquad T_3=Y\oplus E, \quad E\sim\operatorname{Bern}(0.1).

Because $Y$ is contained in $X$ without distortion,

I(Y;X)=H(Y)=1\ \text{bit}.

For $T_1=X$ ,

I(Y;T_1)=1\ \text{bit}.

For $T_2=Y$ ,

I(Y;T_2)=I(Y;Y)=1\ \text{bit}.

$T_3$ is the output of a binary symmetric channel with crossover probability $0.1$ . With a uniform input,

I(Y;T_3) = 1-h_2(0.1) \approx 0.531004\ \text{bits}.

Thus,

\boxed{ I(Y;X)=I(Y;T_1)=I(Y;T_2)=1, \qquad I(Y;T_3)\approx0.531 }.

It is $T_2=Y$ that removes nuisance $N$ without losing target information. The amount of retained input information makes the distinction explicit:

I(X;T_1)=H(X)=2\ \text{bits},

whereas

I(X;T_2)=H(T_2)=1\ \text{bit}.

Good task-specific compression tries to keep $I(Y;T)$ close to $I(Y;X)$ while reducing the unnecessary part of $I(X;T)$ . Intentionally reducing $I(Y;T)$ discards information useful for predicting the target.

Exercise 4. Python: correlation, an MI estimator, and a permutation baseline

Generate three datasets:

Y_{\mathrm{lin}}=X+0.5\varepsilon,

Y_{\mathrm{nonlin}}=X^2+0.3\varepsilon,

Y_{\mathrm{ind}}=\varepsilon,

where $X,\varepsilon\sim\mathcal N(0,1)$ are independent.

For several sample sizes:

compute Pearson correlation;
estimate MI with a $k$ -nearest-neighbor method;
randomly permute $Y$ to obtain a baseline;
repeat the experiment for several seeds.

The goal is to observe nonlinear dependence at near-zero correlation, a nonzero finite-sample baseline, and instability when the sample is small.

Show answer and solution

Here is one reproducible experiment. mutual_info_regression uses a kNN estimator and returns an estimate in nats. The library clips negative numerical estimates to zero, so the permutation baseline usually has a small positive mean.

Python

import numpy as np
import pandas as pd
from sklearn.feature_selection import mutual_info_regression


def estimate_once(n: int, seed: int) -> list[dict[str, float | int | str]]:
    rng = np.random.default_rng(seed)
    x = rng.normal(size=n)

    datasets = {
        "linear": x + 0.5 * rng.normal(size=n),
        "nonlinear": x**2 + 0.3 * rng.normal(size=n),
        "independent": rng.normal(size=n),
    }

    rows = []
    for name, y in datasets.items():
        corr = float(np.corrcoef(x, y)[0, 1])
        mi = float(
            mutual_info_regression(
                x.reshape(-1, 1),
                y,
                n_neighbors=5,
                random_state=seed,
            )[0]
        )
        y_perm = rng.permutation(y)
        mi_perm = float(
            mutual_info_regression(
                x.reshape(-1, 1),
                y_perm,
                n_neighbors=5,
                random_state=seed,
            )[0]
        )
        rows.append(
            {
                "n": n,
                "relation": name,
                "corr": corr,
                "mi_nats": mi,
                "mi_perm_nats": mi_perm,
            }
        )
    return rows


records = []
for n in (200, 1000, 5000):
    for seed in range(30):
        records.extend(estimate_once(n, seed))

df = pd.DataFrame(records)
summary = (
    df.groupby(["n", "relation"])
    .agg(
        corr_mean=("corr", "mean"),
        corr_sd=("corr", "std"),
        mi_mean=("mi_nats", "mean"),
        mi_sd=("mi_nats", "std"),
        perm_mean=("mi_perm_nats", "mean"),
        perm_sd=("mi_perm_nats", "std"),
    )
    .reset_index()
)

with pd.option_context("display.max_rows", None, "display.width", 160):
    print(summary.round(4).to_string(index=False))

For this seed protocol, the output is:

text

   n    relation  corr_mean  corr_sd  mi_mean  mi_sd  perm_mean  perm_sd
 200 independent     0.0057   0.0686   0.0177 0.0287     0.0141   0.0204
 200      linear     0.8934   0.0140   0.8143 0.0761     0.0070   0.0132
 200   nonlinear    -0.0556   0.1287   0.9368 0.0804     0.0151   0.0255
1000 independent     0.0041   0.0269   0.0060 0.0097     0.0045   0.0067
1000      linear     0.8950   0.0062   0.8235 0.0338     0.0086   0.0096
1000   nonlinear    -0.0279   0.0688   1.0913 0.0392     0.0052   0.0076
5000 independent     0.0000   0.0131   0.0037 0.0050     0.0048   0.0052
5000      linear     0.8949   0.0024   0.8127 0.0127     0.0030   0.0050
5000   nonlinear     0.0011   0.0284   1.1378 0.0119     0.0013   0.0030

The main observations are:

For linear dependence, both correlation and MI are large.
For $Y=X^2+\text{noise}$ , mean correlation tends to zero while MI remains large.
For independent data, the finite-sample MI estimate need not be exactly zero.
As $n$ grows, variability decreases and the permutation baseline approaches zero.
The absolute value depends on the estimator, n_neighbors, scaling, and sample size; the comparative pattern matters more here.

Exercise 5. Python: the InfoNCE bound on a known channel

Let $X$ be uniform on $K$ classes. Let $Y=X$ with probability $1-\varepsilon$ and otherwise choose uniformly among the remaining $K-1$ classes.

Derive the exact MI:

I(X;Y) = \log K-h_2(\varepsilon)-\varepsilon\log(K-1).

Use the ideal score

s^*(x,y)=\log\frac{p(y\mid x)}{p(y)}

and estimate the InfoNCE loss by Monte Carlo for $N\in\{4,16,64,256\}$ .

Compare $\log N-\widehat{\mathcal L}_{\mathrm{NCE}}$ with the exact MI.
Verify that $\log N$ limits this bound, not MI itself or representation quality.

Mathematical deepening. Fano's inequality

If $Y$ takes $M$ values and $\widehat Y$ is constructed from $X$ , then

H(Y\mid X) \le h_2(P_e)+P_e\log(M-1),

where $P_e=\Pr(\widehat Y\ne Y)$ . Use the inequality to connect residual uncertainty $H(Y\mid X)$ with an information-theoretic limit on achievable error. Explain separately why the bound may be loose and does not replace construction of the Bayes-optimal classifier.

Show answer and solution

Let $X$ be uniform over $K$ classes. The channel leaves the class unchanged with probability $1-\varepsilon$ and, with probability $\varepsilon$ , chooses uniformly among the other $K-1$ classes.

By symmetry, $Y$ is also uniform, so

H(Y)=\log K.

The conditional distribution has one probability $1-\varepsilon$ and $K-1$ probabilities $\varepsilon/(K-1)$ . Therefore,

H(Y\mid X) = h_2(\varepsilon)+\varepsilon\log(K-1),

and

\boxed{ I(X;Y) = \log K-h_2(\varepsilon)-\varepsilon\log(K-1) }.

The code below uses natural logarithms. Negatives are sampled independently from the marginal $p(y)$ , and the critic is the ideal log-density ratio.

You can also test $\varepsilon=0$ or $1$ : entropy uses $0\log0=0$ , and an impossible pair $(x,y)$ receives a critic score of $-\infty$ . The positive pair is generated by the channel itself, so its score stays finite and the InfoNCE denominator stays positive.

Python

import math
import numpy as np
from scipy.special import logsumexp

K = 64
epsilon = 0.25
rng = np.random.default_rng(20260712)

if K < 2 or not 0.0 <= epsilon <= 1.0:
    raise ValueError("Use K >= 2 and 0 <= epsilon <= 1")

# Exact MI in nats for the K-class symmetric channel.
h_eps = -sum(p * math.log(p) for p in (epsilon, 1.0 - epsilon) if p > 0.0)
mi_exact = math.log(K) - h_eps - epsilon * math.log(K - 1)


def sample_positive(x: np.ndarray) -> np.ndarray:
    """Sample Y from p(y|x) without rejection loops."""
    y = x.copy()
    flip = rng.random(x.size) < epsilon
    offsets = rng.integers(1, K, size=flip.sum())
    y[flip] = (x[flip] + offsets) % K
    return y


def estimate_infonce(n_candidates: int, total_trials: int = 100_000, chunk_size: int = 2_000) -> tuple[float, float]:
    loss_sum = 0.0
    loss_sq_sum = 0.0
    seen = 0

    log_ratio_match = math.log(K * (1.0 - epsilon)) if epsilon < 1.0 else -math.inf
    log_ratio_mismatch = math.log(K * epsilon / (K - 1)) if epsilon > 0.0 else -math.inf

    while seen < total_trials:
        batch = min(chunk_size, total_trials - seen)
        x = rng.integers(0, K, size=batch)
        positive = sample_positive(x)
        negatives = rng.integers(0, K, size=(batch, n_candidates - 1))
        candidates = np.concatenate([positive[:, None], negatives], axis=1)

        scores = np.where(
            candidates == x[:, None],
            log_ratio_match,
            log_ratio_mismatch,
        )
        losses = logsumexp(scores, axis=1) - scores[:, 0]
        loss_sum += float(losses.sum())
        loss_sq_sum += float(np.square(losses).sum())
        seen += batch

    mean_loss = loss_sum / total_trials
    variance = max(loss_sq_sum / total_trials - mean_loss**2, 0.0)
    standard_error = math.sqrt(variance / total_trials)
    return mean_loss, standard_error


print(f"Exact MI: {mi_exact:.6f} nats ({mi_exact / math.log(2):.6f} bits)")
print(" N    loss       bound      log(N)     SE(bound)")
for n_candidates in (4, 16, 64, 256):
    loss, se = estimate_infonce(n_candidates)
    bound = math.log(n_candidates) - loss
    print(
        f"{n_candidates:3d}  {loss:9.6f}  {bound:9.6f}  "
        f"{math.log(n_candidates):9.6f}  {se:9.6f}"
    )

Output:

text

Exact MI: 2.560764 nats (3.694402 bits)
 N    loss       bound      log(N)     SE(bound)
  4   0.429934   0.956360   1.386294   0.002479
 16   0.991886   1.780702   2.772589   0.004612
 64   1.867571   2.291312   4.158883   0.006330
256   3.061057   2.484121   5.545177   0.007008

In this run, all Monte Carlo estimates of the lower bound lie below exact MI. The theoretical guarantee applies to the population bound; its finite-sample estimate can fluctuate upward, which is why the standard error is reported. Increasing $N$ tightens the bound, but for every fixed $N$ ,

\log N-\mathcal L_{\mathrm{NCE}} \le \log N.

The important distinction is that this is a ceiling on the chosen lower bound, not on true $I(X;Y)$ . In the example, for $N=4$ ,

\log 4\approx1.386<2.561=I(X;Y),

so the InfoNCE bound cannot reach the true value even with an ideal critic.

Mathematical deepening. Fano's inequality

From

H(Y\mid X) \le h_2(P_e)+P_e\log(M-1)

we see that if substantial uncertainty about $Y$ remains after observing $X$ , the error probability cannot be arbitrarily small. For example, when $Y$ is uniform,

H(Y\mid X)=H(Y)-I(X;Y)=\log M-I(X;Y).

The smaller $I(X;Y)$ is relative to $\log M$ , the more uncertainty a classifier would have to remove without available signal—which is impossible.

Fano usually provides a lower bound, not the exact Bayes error. It may be loose and does not tell us which model or training procedure attains the optimum.