Shannon Entropy and Classical Information Measures

Shannon's bits are the working currency of the digital world and the launchpad of its quantum successor. Every general-purpose compressor — the entropy coders inside ZIP, PNG, JPEG, H.264, and modern neural codecs — is engineered to approach the source coding limit $H(X)$ per symbol, and arithmetic and asymmetric-numeral-system coders get within fractions of a bit of it on real data. The noisy channel coding theorem, $C=\max_{p_X}I(X;Y)$, is the target that turbo codes, LDPC codes, and polar codes were designed to reach, and 5G and deep-space links now operate within a fraction of a decibel of the Shannon limit. Relative entropy is the loss function at the heart of machine learning — training a classifier by cross-entropy is minimizing $D(p\,\|\,q)$ between the data and the model — and it supplies the error exponents of hypothesis testing through Stein's lemma. The frontier is the quantum lift: replacing distributions by density operators sends $H\to S(\rho)$, $I\to I(A;B)_\rho$, and $D\to S(\rho\,\|\,\sigma)$, and the open problems there — the additivity of channel capacities, the exact rates for entanglement-assisted communication, the role of strong subadditivity in constraining many-body entanglement — are all posed in the language Shannon built, with the classical inequalities of this article as the constraints they must respect.

Think of entropy as the expected number of yes/no questions needed to pin down an outcome under the smartest questioning strategy. For a uniform distribution over eight symbols you always need $3=\log_2 8$ questions; for a skewed source you can do better on average by asking about the likely symbols first — and the best any strategy can do is exactly $H(X)$ questions per symbol, a limit that Huffman and arithmetic codes approach. The entropy is therefore not a description of a message but a property of the source that emits it: it is the average price, in bits, of resolving one draw. The first figure makes the shape of this price concrete for the simplest possible source, a single biased coin, where the whole story lives on one curve.

The measures that describe pairs of variables are best seen as areas. Draw the uncertainty of $X$ as one disc and of $Y$ as another; where they overlap is the information the two share, and the mutual information $I(X;Y)$ is exactly that overlap. The joint entropy $H(X,Y)$ is the total area of the union, the conditional entropy $H(X\mid Y)$ is the crescent of $X$ that survives once $Y$ is known, and the identity $I(X;Y)=H(X)+H(Y)-H(X,Y)$ is just inclusion–exclusion for two sets. The second figure is that Venn diagram made quantitative — the picture is exact for classical variables and, as the article on quantum mutual information will show, only a heuristic once operators enter.

Underneath both figures sits the reason a single number can be a hard limit at all: the asymptotic equipartition property, the law of large numbers for information. Over a long run of $n$ independent draws the sequences split sharply into a typical set of about $2^{nH(X)}$ members, each occurring with probability near $2^{-nH(X)}$, plus an exponentially negligible remainder. Compression is then nothing more than handing each typical sequence an index — and there are only $2^{nH(X)}$ of them, so $nH(X)$ bits suffice. Relative entropy measures the cost of getting the source wrong: build a code tuned to a model $q$ while the data actually follow $p$, and you overspend by exactly $D(p\,\|\,q)$ bits per symbol.

The definition is an expectation of surprisal. Each outcome $x$ carries $-\log_2 p(x)$ bits of surprise — larger for rarer events — and the entropy averages this over the source, so it is small when a few symbols dominate and large when probability is spread evenly.

where: $X$ — discrete random variable with alphabet $\mathcal{X}$; $p(x)$ — probability $\Pr[X=x]$, with $\sum_x p(x)=1$; $-\log_2 p(x)$ — surprisal (self-information) of outcome $x$, in bits; $H(X)$ — expected surprisal $\mathbb{E}[-\log_2 p(X)]$. Reading it: $H(X)$ is the average number of bits an ideal code spends per symbol, and the convention $0\log_2 0:=0$ (justified by $\lim_{p\to0^+}p\log_2 p=0$) lets zero-probability symbols drop out silently. The entropy is pinned between two extremes: it cannot be negative, and it cannot exceed the entropy of the uniform distribution on the same alphabet. Both bounds are sharp.

where: $|\mathcal{X}|$ — the number of symbols carrying nonzero probability. The lower bound is attained by a deterministic source and the upper bound by the uniform one; the gap $\log_2|\mathcal{X}|-H(X)$ turns out to be itself a relative entropy, which is why it can never be negative. For a pair of variables the joint entropy is the entropy of the combined outcome, treating $(X,Y)$ as one random variable over the product alphabet.

where: $p(x,y)$ — joint probability $\Pr[X=x,\,Y=y]$. It measures the total uncertainty in learning both variables at once, and reduces to $H(X)+H(Y)$ exactly when $X$ and $Y$ are independent. Conditional entropy is the uncertainty in $X$ that remains after $Y$ is revealed, averaged over what $Y$ might be. Two equivalent forms — an average of conditional entropies, and a difference of joint and marginal — coincide by the product rule.

where: $H(X\mid Y{=}y)=-\sum_x p(x\mid y)\log_2 p(x\mid y)$ — entropy of the conditional law given a specific $y$; $p(x\mid y)$ — conditional probability $\Pr[X=x\mid Y=y]$. Because it is a probability-weighted average of ordinary (nonnegative) entropies, the classical $H(X\mid Y)\ge0$ always — a fact that fails quantumly and signals entanglement when it does. Mutual information is the reduction in uncertainty about $X$ that knowing $Y$ buys — symmetrically, the information the two share. It has three faces: a combination of entropies, a difference of a marginal and a conditional, and a divergence.

where: $I(X;Y)$ — shared information, equal to $H(X)-H(X\mid Y)=H(Y)-H(Y\mid X)$. It is symmetric, nonnegative, and vanishes precisely when $X$ and $Y$ are independent; it is the classical prototype of the quantum mutual information $I(A;B)_\rho$. Relative entropy — the Kullback–Leibler divergence — is the master quantity. It is a directed, asymmetric measure of how distinguishable a true distribution $p$ is from a reference $q$, and it is the penalty paid for modelling $p$ by $q$.

where: $q(x)$ — reference distribution; $D=+\infty$ if $p(x)>0=q(x)$ for some $x$; the value is generally asymmetric, $D(p\,\|\,q)\ne D(q\,\|\,p)$. Its nonnegativity (Gibbs' inequality, derived below) is the single fact from which the bounds on $H$, the positivity of $I$, subadditivity, and data processing all descend. Two structural identities close the toolkit. The chain rule decomposes the entropy of many variables into a telescoping sum of conditionals, and the data-processing inequality forbids any post-processing from manufacturing information.

where: $X_1,\dots,X_n$ — jointly distributed variables; $X\to Y\to Z$ — a Markov chain, meaning $Z$ is conditionally independent of $X$ given $Y$. The chain rule is the additive backbone of every multivariate calculation; the data-processing inequality is the formal statement that you cannot learn more about $X$ by looking at a processed copy $Z$ than by looking at $Y$ itself.

Special distributions expose the meaning and the extreme values of the entropy, and the divergence between them.

1 · A dyadic source, its entropy, and an optimal code (fully worked)

A source emits four symbols $\{a,b,c,d\}$ with probabilities $\{\tfrac12,\tfrac14,\tfrac18,\tfrac18\}$. Find its entropy, exhibit a code that meets the entropy bound exactly, and compute the relative-entropy penalty of instead coding it as if it were uniform.

Step 1. Entropy from the definition. Each surprisal is $-\log_2 p$: symbol $a$ carries $-\log_2\tfrac12=1$ bit, $b$ carries $2$ bits, and $c,d$ each carry $3$ bits. Averaging,

Because every probability is a power of two (a dyadic source), the surprisals are whole numbers of bits.

Step 2. A code that hits the bound. Assign codewords of length equal to each surprisal — $a\to0$, $b\to10$, $c\to110$, $d\to111$ (a Huffman code). This prefix-free code has average length $\tfrac12(1)+\tfrac14(2)+\tfrac18(3)+\tfrac18(3)=1.75$ bits per symbol, equal to $H(X)$ with no gap. Dyadic sources are exactly the case where an integer-length code achieves the entropy; for general sources Huffman coding lands within one bit and arithmetic coding closes the remainder asymptotically.

Step 3. The penalty for the wrong model. Suppose you instead used a flat code tuned to the uniform distribution $q=\{\tfrac14,\tfrac14,\tfrac14,\tfrac14\}$ — two bits for every symbol. The overspend per symbol is the relative entropy:

Consistency check: the flat code costs exactly $2$ bits/symbol, and indeed $H(X)+D(p\,\|\,q)=1.75+0.25=2$ bits. This also confirms the identity $\log_2|\mathcal{X}|-H(X)=D(p\,\|\,u)$, since $\log_2 4-1.75=0.25$. Answers: $H=1.75$ bits, an optimal code averages $1.75$ bits/symbol, and the uniform-model penalty is $0.25$ bit/symbol.

2 · Mutual information through a noisy channel

A uniformly random input bit $X\in\{0,1\}$ passes through a binary symmetric channel that flips it with probability $p=0.1$, producing $Y$. How much does observing $Y$ tell you about $X$?

Step 1. By symmetry the output $Y$ is also uniform, so $H(Y)=1$ bit. Given the input, the only remaining randomness is the flip, so $H(Y\mid X)=H_2(p)=H_2(0.1)$.

Step 2. Evaluate the binary entropy of the noise: $H_2(0.1)=-0.1\log_2 0.1-0.9\log_2 0.9\approx\mathbf{0.469\ \text{bit}}$ (the same value as $H_2(0.9)$ by symmetry).

Step 3. Mutual information is the output uncertainty minus the noise: $I(X;Y)=H(Y)-H(Y\mid X)=1-0.469=\mathbf{0.531\ \text{bit}}$. Since the uniform input maximizes $I$ for this channel, this is also the channel capacity $C=1-H_2(p)=0.531$ bit per use — the most reliable information a $10\%$-flip channel can carry. Answer: each use of the channel conveys $I(X;Y)=0.531$ bit, and this equals its capacity.

The classical information measures are the work of one decisive paper and a small circle around it — a wartime cryptanalyst who saw that "information" could be measured in bits, that a source has an irreducible rate, and that noise sets a hard but achievable ceiling on communication.

Texts. Nielsen and Chuang, Quantum Computation and Quantum Information, Ch. 11–12 · Cover and Thomas, Elements of Information Theory, Ch. 2–3 · Wilde, Quantum Information Theory, Ch. 10 · Preskill, Lecture Notes on Quantum Computation, Ch. 10 · Watrous, The Theory of Quantum Information, Ch. 5 · Shannon, A Mathematical Theory of Communication, Bell Syst. Tech. J. (1948) · Mermin, Quantum Computer Science, Ch. 5. Key numerical anchors: $H_2(0.5)=1$ bit and $H_2(0.9)=H_2(0.1)\approx0.469$ bit by direct computation; the dyadic source $\{\tfrac12,\tfrac14,\tfrac18,\tfrac18\}$ has $H=1.75$ bits with a Huffman code of average length $1.75$, and $D(p\,\|\,u)=0.25$ bit matching $\log_2 4-H=0.25$; the binary symmetric channel with $p=0.1$ has $I=C=1-H_2(0.1)=0.531$ bit; the Gibbs inequality rests on $\ln t\le t-1$ and the AEP set-size bound is $|A_\epsilon^{(n)}|\le2^{n(H+\epsilon)}$.

Prerequisites. Probability theory (discrete random variables, joint and conditional distributions) · Convexity and Jensen's inequality · Logarithms and basic asymptotics. Leads to. Von Neumann Entropy · Quantum Relative Entropy · Quantum Conditional Entropy and Mutual Information · Schumacher Data Compression · Holevo Bound · Data-Processing Inequality.

Ask the tutor: Ask me to walk you through why $H(X)$ is the exact compression limit — or to show, step by step, how every inequality here falls out of the single fact that relative entropy is nonnegative.