Shannon Entropy & Mutual Information

Overview & Motivation

How much information does a random variable carry? How many bits do we need, at minimum, to encode a message? When two variables are statistically dependent, how much does knowing one tell us about the other?

These questions have precise, quantitative answers — and they all flow from a single idea that Claude Shannon published in 1948: entropy. Shannon showed that the uncertainty in a random variable has a unique, canonical measure, and that this measure controls the fundamental limits of data compression, communication, and statistical inference.

For machine learning, information theory is not optional background. Cross-entropy loss — the default objective for classification — is an information-theoretic quantity. Mutual information drives feature selection. The data processing inequality explains why deep representations can lose but never create information about the input. The maximum-entropy principle connects to Bayesian inference through the choice of priors. And KL Divergence & f-Divergences, the next topic on this track, builds directly on the entropy framework we develop here.

What We Cover

1. Information content and Shannon entropy — the surprise of an outcome and the average surprise of a distribution
2. Joint and conditional entropy — uncertainty in pairs of variables and the chain rule
3. Mutual information — the symmetric measure of statistical dependence
4. The data processing inequality — why post-processing cannot create information
5. Differential entropy — the continuous extension and the maximum-entropy role of the Gaussian
6. Source coding and compression — Shannon’s theorem, Kraft’s inequality, and Huffman coding
7. Entropy rate — entropy for stochastic processes and Markov chains
8. Connections to ML — cross-entropy loss, MI feature selection, and the InfoMax principle

Prerequisites

This topic builds on:

• Measure-Theoretic Probability — entropy is defined as the expectation $E[-\log p(X)]$, differential entropy requires the Lebesgue integral, and conditional entropy uses conditional expectation

---

Information Content & Shannon Entropy

Imagine playing a guessing game. Your friend picks a card from a deck and you must guess which one. If the deck has 2 cards, one guess suffices — that’s 1 bit of uncertainty. A deck of 8 cards takes 3 guesses in the worst case — 3 bits. The pattern is clear: the uncertainty in a uniform draw over $n$ outcomes is $\log_2 n$ bits.

But what if the outcomes are not equally likely? Shannon’s key insight was to define the information content (or surprise) of a single outcome, and then take the average to get the entropy.

The choice of $\log_2$ gives units of bits. Using $\ln$ gives nats; using $\log_{10}$ gives hartleys. The choice of base is a convention — we use bits throughout this topic.

Entropy is the average surprise — the expected number of bits needed to encode a randomly drawn outcome. It is the fundamental measure of uncertainty in information theory.

The binary entropy function is the special case for a Bernoulli random variable with parameter $p$:

$H_b(p) = -p \log_2 p - (1-p) \log_2(1-p)$

This reaches its maximum of $1$ bit at $p = 1/2$ (a fair coin) and drops to $0$ at $p = 0$ or $p = 1$ (a certain outcome).

Properties of Entropy

Explore the interactive visualization below. Drag the bars to change the probability distribution and watch entropy respond in real time.

Outcomes (k):23468UniformPeaked

---

Joint Entropy & Conditional Entropy

When we have two random variables, we can ask about their combined uncertainty and how much knowing one reduces uncertainty about the other.

The chain rule connects these quantities.

In plain language: information can only reduce (or maintain) uncertainty, never increase it. Knowing something extra about the world cannot make you more confused on average.

---

Mutual Information

Mutual information captures how much knowing one variable tells us about another. It is the fundamental measure of statistical dependence in information theory.

Mutual information is the KL divergence from the joint distribution to the product of marginals: $I(X;Y) = D_{KL}(p_{XY} \| p_X p_Y)$. It measures how far the joint distribution is from independence.

This is remarkable: conditioning is asymmetric ($H(Y|X) \neq H(X|Y)$ in general), but mutual information is perfectly symmetric. Knowing $X$ tells you the same amount about $Y$ as knowing $Y$ tells you about $X$.

The Information Diagram

The relationships between $H(X)$, $H(Y)$, $H(X,Y)$, $H(X|Y)$, $H(Y|X)$, and $I(X;Y)$ are best visualized as a Venn diagram — the information diagram. Two overlapping circles represent $H(X)$ and $H(Y)$; the overlap is $I(X;Y)$; the left crescent is $H(X|Y)$; the right crescent is $H(Y|X)$; and the union is $H(X,Y)$.

|X|:234|Y|:234IndependentCorrelatedNoisyCustom

Conditional Mutual Information and Chain Rule

---

The Data Processing Inequality

The data processing inequality (DPI) is one of the most important results in information theory for machine learning. It formalizes a simple but powerful idea: you cannot create information by processing data.

The DPI has profound implications for representation learning. Every layer in a neural network processes its input: if we have $X \to Z_1 \to Z_2 \to \cdots \to Z_L$, then $I(X; Z_1) \geq I(X; Z_2) \geq \cdots \geq I(X; Z_L)$. Information about the input can only decrease through the network. A good representation is one that preserves the relevant information about the target while discarding noise.

Explore the DPI interactively — adjust the channel type and noise level to see how information degrades through processing.

Channel:Binary SymmetricGaussianQuantizationDeterministic (equality)ε:0.150

---

Differential Entropy

What happens when we move from discrete to continuous random variables? The naive approach — replacing sums with integrals — gives differential entropy, but with some important caveats.

Unlike discrete entropy, differential entropy can be negative — it is not a true measure of “information” in the same absolute sense. However, differences of differential entropies are well-behaved, and mutual information $I(X;Y) = h(X) - h(X|Y)$ is non-negative even for continuous variables.

Key properties

Translation invariance. $h(X + c) = h(X)$ for any constant $c$. Shifting a distribution does not change its uncertainty.

Non-invariance under scaling. If $Y = aX$ for $a \neq 0$, then $h(Y) = h(X) + \log_2 |a|$. Stretching a distribution increases its entropy; compressing it decreases entropy. This is why differential entropy can be negative — concentrate a distribution enough and $h(X) < 0$.

Maximum Entropy Distribution

This result explains why Gaussians appear everywhere in statistics and ML: they are the “least informative” distributions for a given variance. When we assume Gaussian noise or Gaussian priors, we are making the maximum-entropy assumption — committing to the distribution that introduces the least extra structure beyond the constraint on variance.

Mutual information for continuous variables

While differential entropy has quirks (negativity, scale-dependence), mutual information remains perfectly well-defined for continuous variables:

$I(X;Y) = h(X) + h(Y) - h(X,Y) = \int \int f(x,y) \log_2 \frac{f(x,y)}{f(x) f(y)} \, dx \, dy$

This is non-negative and equals zero iff $X$ and $Y$ are independent, just as in the discrete case. The scale-dependent artifacts cancel in the difference.

---

Source Coding & Compression

Shannon entropy is not just an abstract measure of uncertainty — it has a concrete operational meaning: the entropy of a source is the fundamental limit of lossless data compression. Shannon’s source coding theorem makes this precise.

Prefix codes and Kraft’s inequality

Shannon’s source coding theorem

The Huffman algorithm builds an optimal prefix code by iteratively merging the two lowest-probability symbols. Explore the construction below.

Symbols (k):23458Hide Tree

Sym	p(x)	Code	ℓ(x)
A	0.438	0	1
B	0.219	10	2
C	0.146	110	3
D	0.109	1111	4
E	0.088	1110	4

H(X):2.064 bits

E[ℓ]:2.102 bits

Gap (E[ℓ] − H):0.038

H(X) ≤ E[ℓ] < H(X) + 1

Code blocks: Huffman coding in Python

import heapq

class HuffmanNode:
    def __init__(self, symbol=None, prob=0, left=None, right=None):
        self.symbol = symbol
        self.prob = prob
        self.left = left
        self.right = right

    def __lt__(self, other):
        return self.prob < other.prob

def build_huffman_tree(symbols, probs):
    heap = [HuffmanNode(s, p) for s, p in zip(symbols, probs)]
    heapq.heapify(heap)
    while len(heap) > 1:
        left = heapq.heappop(heap)
        right = heapq.heappop(heap)
        merged = HuffmanNode(prob=left.prob + right.prob, left=left, right=right)
        heapq.heappush(heap, merged)
    return heap[0]

def get_codes(node, prefix='', codes=None):
    if codes is None:
        codes = {}
    if node.symbol is not None:
        codes[node.symbol] = prefix if prefix else '0'
    else:
        if node.left:
            get_codes(node.left, prefix + '0', codes)
        if node.right:
            get_codes(node.right, prefix + '1', codes)
    return codes

---

Entropy Rate

So far we have studied entropy for single random variables and pairs. For stochastic processes — sequences of random variables — the relevant quantity is the entropy rate: the per-symbol uncertainty in the long run.

For an i.i.d. process, $\mathcal{H} = H(X_1)$ — each symbol carries its full entropy. But for processes with memory (like Markov chains), the entropy rate is strictly less than $H(X_1)$ because past observations reduce uncertainty about the next symbol.

The entropy rate of a Markov chain is a weighted average of the entropies of each row of the transition matrix, weighted by the stationary distribution. States visited more often contribute more to the overall rate.

---

Computational Notes

Computing entropy in NumPy

import numpy as np

def entropy(probs):
    """Shannon entropy in bits. Convention: 0 log 0 = 0."""
    p = np.asarray(probs, dtype=float)
    p = p[p > 0]  # filter zeros
    return -np.sum(p * np.log2(p))

# Examples
probs_uniform = np.array([0.25, 0.25, 0.25, 0.25])
print(f"Uniform(4): H = {entropy(probs_uniform):.4f} bits")  # 2.0000

probs_peaked = np.array([0.9, 0.05, 0.03, 0.02])
print(f"Peaked:     H = {entropy(probs_peaked):.4f} bits")    # 0.6095

Mutual information from a joint table

def mutual_information(joint):
    """I(X;Y) from a 2D joint probability array."""
    joint = np.asarray(joint, dtype=float)
    p_x = joint.sum(axis=1)
    p_y = joint.sum(axis=0)
    return entropy(p_x) + entropy(p_y) - entropy(joint.ravel())

joint = np.array([[0.3, 0.1],
                   [0.1, 0.5]])
print(f"I(X;Y) = {mutual_information(joint):.4f} bits")

Plug-in vs. k-NN mutual information estimation

For continuous data, we can estimate MI using either a plug-in estimator (discretize into bins, compute the histogram MI) or the k-nearest-neighbor estimator of Kraskov, Stögbauer & Grassberger (2004), which avoids binning artifacts:

import numpy as np

# Plug-in estimator: discretize and compute
def mi_plugin(x, y, bins='auto'):
    """Plug-in MI estimator via 2D histogram."""
    hist_2d, _, _ = np.histogram2d(x, y, bins=bins)
    hist_2d = hist_2d / hist_2d.sum()  # normalize to joint PMF
    p_x = hist_2d.sum(axis=1)
    p_y = hist_2d.sum(axis=0)
    return entropy(p_x) + entropy(p_y) - entropy(hist_2d.ravel())

The plug-in estimator is biased for small samples (tends to overestimate MI) and sensitive to bin width. The k-NN estimator is consistent and adaptive, making it the preferred method for continuous MI estimation.

Cross-entropy loss and entropy

The cross-entropy loss used in classification is an information-theoretic quantity:

$H(p, q) = -\sum_i p_i \log_2 q_i = H(p) + D_{KL}(p \| q)$

For one-hot labels ($p$ is a point mass), $H(p) = 0$, so $H(p, q) = D_{KL}(p \| q)$. Minimizing cross-entropy loss is equivalent to minimizing the KL divergence from the model’s predicted distribution to the true label distribution.

import torch
import torch.nn.functional as F

# PyTorch cross-entropy loss
logits = torch.tensor([[1.0, 2.0, 0.5, 0.1]])  # raw model outputs
target = torch.tensor([1])                        # true class

loss = F.cross_entropy(logits, target)
print(f"Cross-entropy loss: {loss.item():.4f} nats")

# This equals -log(softmax(logits)[target])
probs = F.softmax(logits, dim=1)
manual_loss = -torch.log(probs[0, target[0]])
print(f"Manual check:       {manual_loss.item():.4f} nats")

Mutual information for feature selection

Rank features by their mutual information with the target variable to identify the most informative features:

$I(X_i; Y) = H(Y) - H(Y | X_i)$

This non-parametric criterion captures arbitrary (not just linear) dependencies, making it more powerful than correlation for feature selection in classification tasks.

---

Connections & Further Reading

Shannon entropy opens the door to a rich web of information-theoretic quantities and their applications across machine learning, statistics, and beyond.

Downstream on this track

• KL Divergence & f-Divergences — the asymmetric divergence $D_{KL}(p \| q) = H(p, q) - H(p)$ generalizes to the broader family of $f$-divergences, each inducing a different geometry on the space of distributions.
• Rate-Distortion Theory — Shannon’s lossy source coding theorem: the minimum rate $R(D)$ for encoding a source at distortion level $D$ is an optimization over mutual information.
• Minimum Description Length — model selection via code length: the best model minimizes the total description length (model code + data-given-model code), connecting entropy to statistical learning theory.

Cross-track connections

• Measure-Theoretic Probability — entropy is $E[-\log p(X)]$; differential entropy requires the Lebesgue integral; conditional entropy uses conditional expectation via the Radon–Nikodym theorem.
• Convex Analysis — entropy is concave in $p$; Jensen’s inequality proves uniform maximality; channel capacity and rate-distortion optimization are convex programs.
• Information Geometry & Fisher Metric — the Fisher metric is the Hessian of KL divergence, which is defined in terms of entropy. The entropy and divergence functions developed here are the starting point for the geometric structure on statistical manifolds.
• Bayesian Nonparametrics — the maximum entropy principle selects the least informative prior consistent with known constraints, connecting entropy to Bayesian inference and the choice of non-informative priors.
• Graph Laplacians & Spectrum — the entropy of a random walk’s stationary distribution $H(\boldsymbol{\pi})$ measures graph regularity. On a $d$-regular graph, $\boldsymbol{\pi}$ is uniform with maximum entropy $\log_2 n$. The spectral gap governs the mixing rate — how fast entropy increases toward equilibrium.