Information Theory and Entropy

Information theory provides a language for uncertainty and the limits of communication. Build this branch in the following order:

1. self-information and entropy;
2. joint and conditional entropy;
3. mutual information and independence;
4. cross-entropy and Kullback–Leibler divergence;
5. source coding and compression limits;
6. noisy channels and channel capacity;
7. connections to probabilistic modeling and machine-learning objectives.

This reference covers finite discrete distributions and their use in coding and prediction. Start with probability, conditional probability, and expectation. MIT OpenCourseWare 6.050J develops the broader communication and physical-system topics above.

Surprise and average uncertainty

If an outcome has probability $p>0$, its self-information is $-\log_2 p$ bits. Independent outcomes have multiplying probabilities, so their information adds. A certain outcome carries zero bits; a probability-$1/8$ outcome carries 3 bits. This measures surprise under a model, not truth, usefulness, or meaning.

For a random variable $X$ with probabilities $p(x)$, entropy is expected self-information:

$$H(X)=-\sum_x p(x)\log_2 p(x),\qquad 0\log_2 0:=0.$$

For $k$ possible outcomes, $0\le H(X)\le\log_2 k$, with the maximum at the uniform distribution. A fair coin has entropy 1 bit; a coin with probabilities $(3/4,1/4)$ has $H\approx0.811$ bits. The rarer outcome carries 2 bits, but entropy averages over both outcomes.

Conditioning and shared information

Joint entropy measures uncertainty in the pair $(X,Y)$. Conditional entropy averages the uncertainty remaining in $Y$ after observing $X$:

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

Mutual information $I(X;Y)$ is nonnegative and is zero exactly when $X$ and $Y$ are independent. Conditioning cannot increase entropy on average, although a particular observation can increase uncertainty. If $Y=X$ for a fair coin, $H(Y\mid X)=0$ and $I(X;Y)=1$ bit. For two independent fair coins, $H(X,Y)=2$ and $I(X;Y)=0$. Dependence alone does not establish causation.

Open full-size image

For two finite discrete variables, read the overlap as shared information. On average, observing X removes that part of the uncertainty about Y; the remaining right-hand region is H(Y | X). The regions illustrate entropy identities, not sets of possible outcomes. The figure writes I(X, Y) for the same quantity denoted I(X; Y) here.

Zhang et al., Dive into Deep Learning, Figure 22.11.1. · CC BY-SA 4.0

Cross-entropy and model mismatch

Let $p$ be the actual distribution and $q$ the predictive distribution on the same outcomes. Using base-2 logs,

$$H(p,q)=-\sum_x p(x)\log_2 q(x) =H(p)+D_{\mathrm{KL}}(p\|q),$$ $$D_{\mathrm{KL}}(p\|q)=\sum_{x:p(x)>0}p(x)\log_2\frac{p(x)}{q(x)}.$$

Terms with $p(x)=0$ contribute zero and are omitted. If $q(x)=0$ where $p(x)>0$, these quantities are infinite. Otherwise KL divergence is nonnegative and vanishes exactly when the distributions agree. It is not a distance metric: it is generally asymmetric and does not satisfy the triangle inequality.

For $p=(3/4,1/4)$ and $q=(1/2,1/2)$, cross-entropy is 1 bit and KL divergence is about $0.189$ bits. Minimizing cross-entropy over $q$ minimizes KL because $H(p)$ is fixed. In classification, averaging $-\log q(y_i\mid x_i)$ over observed labels estimates an expected log loss; natural logs give nats rather than bits. Low training loss alone does not establish performance on new data.

What entropy says about compression

For a known finite source distribution, the optimal binary prefix code has expected length $L$ satisfying $H(X)\le L<H(X)+1$. Entropy is an average lower bound, not a fractional-length promise for each symbol. The biased coin still needs one bit per symbol with a one-symbol binary prefix code. For independent, identically distributed symbols, coding blocks of length $n$ reduces the possible overhead per symbol below $1/n$ bit. Correlated sources require conditional structure or entropy rates; their single-symbol entropy need not be the best per-symbol limit.

Continuous variables need a separate treatment: differential entropy depends on coordinates and can be negative, so it is not directly the number of bits needed to store a real value. Precision must be specified before discussing such storage costs.

My reading · Opened notes are remembered in this browser.