Mutual information

Background

Mutual information $I(X;Y)$ quantifies how much knowing one variable reduces uncertainty about another — the information they share, in bits. It is zero exactly when $X$ and $Y$ are independent, and equals $H(X)$ when $Y$ fully determines $X$. It is widely used for feature selection and as a model-agnostic measure of dependence (it captures nonlinear relationships that correlation misses).

Problem statement

Implement mutual_information(x, y) from paired discrete samples:

$$I(X;Y) = \sum_{a,b} p(a,b)\,\log_2\frac{p(a,b)}{p(a)\,p(b)}$$

Estimate $p(a,b)$, $p(a)$, $p(b)$ from empirical frequencies; sum only over pairs with $p(a,b)>0$. Return bits.

Input

• x, y — 1-D arrays of the same length with discrete (hashable) values.

Output

A float: the mutual information in bits ($\ge 0$).

Examples

Example 1

Input:  x = [0, 0, 1, 1], y = [0, 1, 0, 1]
Output: 0.0

Explanation: every (x, y) pair occurs once, so $p(a,b)=0.25=p(a)p(b)$ for all pairs — x and y are independent and share no information.

Constraints

• Use empirical frequencies for the joint and both marginals.
• Sum over pairs with positive joint probability only (skip $p(a,b)=0$).
• Use $\log_2$ for an answer in bits.

Notes

• When $Y = X$, mutual information equals the entropy $H(X)$ — they share everything.
• MI is symmetric, $I(X;Y)=I(Y;X)$, and nonnegative; it generalizes correlation to any (including nonlinear) dependence.