Entropy & Mutual Information

Information theory begins with uncertainty over possible messages, not with their semantic meaning. If a discrete random variable $X$ has outcomes $x$ with probabilities $p(x)$, its entropy in bits is

$$H(X)=-\sum_x p(x)\log_2 p(x).$$

The contribution $-\log_2 p(x)$ is the self-information of observing $x$: a rare outcome is more surprising than a common one. Entropy is its expectation.

Why the logarithm appears #

Independent events should add information. If events with probabilities $p$ and $q$ occur independently, their joint probability is $pq$. The logarithm is the continuous transformation satisfying

$$-\log(pq)=-\log p-\log q.$$

Changing log base changes units: base 2 gives bits, base $e$ nats. The minus sign makes information nonnegative because probabilities do not exceed one.

Entropy is zero when one outcome is certain. For $n$ equiprobable outcomes it is $\log_2 n$, the maximum possible entropy on that finite alphabet.

Worked example #

Let $X$ take values normal, slow, failed with probabilities $0.75$, $0.20$, $0.05$:

$$H(X)=-(0.75\log_2 0.75+0.20\log_2 0.20+0.05\log_2 0.05) \approx0.99\ \text{bits}.$$

There are three labels, but uncertainty is below $\log_2 3\approx1.585$ bits because one label dominates. Entropy does not say whether “failed” is important; it only describes the distribution.

Joint and conditional entropy #

For variables $X$ and $Y$,

$$H(X,Y)=-\sum_{x,y}p(x,y)\log_2p(x,y).$$

Conditional entropy is

$$H(X\mid Y)=\sum_y p(y)H(X\mid Y=y).$$

The chain rule follows by factoring $p(x,y)=p(y)p(x\mid y)$:

$$H(X,Y)=H(Y)+H(X\mid Y).$$

It says the average description of the pair can be separated into the information needed for $Y$ plus what remains for $X$ after $Y$ is known.

Mutual information #

Mutual information is the expected reduction in uncertainty about one variable after observing the other:

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

Equivalently,

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

This is zero exactly when $X$ and $Y$ are independent. It is symmetric and nonnegative. A perfect copy has $I(X;Y)=H(X)$.

Mutual information detects nonlinear statistical dependence that zero correlation can miss. It still does not establish causality: a common cause, selection effect or data leakage can produce high $I(X;Y)$.

flowchart LR
  HX["H(X)"] --> I["shared uncertainty\nI(X;Y)"]
  HY["H(Y)"] --> I
  HX --> CX["remaining H(X|Y)"]
  HY --> CY["remaining H(Y|X)"]

KL divergence and cross-entropy #

For distributions $p$ and $q$ on the same support,

$$D_{KL}(p\|q)=\sum_x p(x)\log\frac{p(x)}{q(x)}\ge0.$$

It is an expected excess log loss from using $q$ when data follow $p$. It is not symmetric and is not a distance. If $q(x)=0$ where $p(x)>0$, the divergence is infinite.

Cross-entropy is

$$H(p,q)=-\sum_x p(x)\log q(x)=H(p)+D_{KL}(p\|q).$$

When $p$ is fixed, minimizing cross-entropy over $q$ minimizes KL divergence. This identity is the foundation for many probabilistic learning losses.

Mutual information is itself a KL divergence:

$$I(X;Y)=D_{KL}\!\left(p(x,y)\,\|\,p(x)p(y)\right).$$

It measures how far the joint distribution is from independence.

Continuous variables require care #

Replacing the sum with an integral yields differential entropy

$$h(X)=-\int p(x)\log p(x)\,dx.$$

Unlike discrete entropy, $h(X)$ depends on coordinate scale and can be negative. It is not the number of bits needed to encode an exact real value. Mutual information and relative entropy remain coordinate-invariant under suitable invertible transformations, which is why they are usually safer continuous quantities.

Estimation is the hard part #

Plugging empirical frequencies into the formulas works for small, well-sampled discrete alphabets. With many categories or continuous/high-dimensional variables, estimates can be strongly biased and sensitive to binning, kernels or model choice. Always report estimator, sample size, smoothing, uncertainty and validation.

What entropy does not measure #

• semantic meaning or truth;
• practical value of a message;
• causal influence;
• algorithmic complexity of one individual object;
• thermodynamic entropy without a physical mapping and units;
• security merely because output entropy looks large.

Entropy answers a precise probabilistic question. Its power comes from keeping that question precise rather than treating “information” as one universal substance.