Shannon Entropy Recap

You flip a coin. Before the flip, you don't know the outcome — that's uncertainty. After the flip, you do — that's information. The amount of uncertainty you lost is exactly the amount of information you gained. Shannon entropy puts a number on both.

This chapter is the classical warm-up for the quantum version. Every quantum-information quantity in Part 20 — von Neumann entropy, conditional entropy, quantum mutual information, quantum channel capacity — is a direct analogue of a classical Shannon quantity. If the classical story is fluent, the quantum story is mostly a change of notation: p(x) \to \rho, \sum \to \text{tr}, \log \to matrix log. If the classical story is hazy, the quantum chapters will feel like alchemy. So: a clean recap, at the level a JEE-Advanced student can follow, of Shannon's 1948 framework.

What entropy is trying to measure

Before the formula, the intuition. Two scenarios:

• Scenario A. Your friend is about to tell you the result of today's cricket toss at the Wankhede. There are two outcomes, heads or tails, each with probability 1/2. How uncertain are you? Fully uncertain — you have no idea which.
• Scenario B. Your friend is about to tell you whether the Sun rose this morning. There are two outcomes. How uncertain are you? Zero. You already know.

Both scenarios have two possible outcomes, yet the uncertainty is very different. The difference is in the probabilities. Entropy is the function that takes a probability distribution and spits out a single number quantifying how uncertain you are about a random draw from it.

The right number should obey a few common-sense rules:

1. Certain outcome → zero uncertainty. If one outcome has probability 1, entropy is 0.
2. Uniform → maximum uncertainty. For n equally likely outcomes, the entropy should be as large as it gets for that n.
3. More outcomes → more room for uncertainty. A uniform distribution over 4 outcomes should be more uncertain than a uniform distribution over 2.
4. Independent variables add. If X and Y are independent random variables, the uncertainty of the pair (X, Y) should be the sum of the individual uncertainties.

Shannon (1948) showed that these requirements — plus a weak continuity condition — force the formula up to an overall constant. That formula is the thing you are about to meet.

Shannon entropy of a single random variable

Reading the definition. The quantity -\log_2 p(x) is the surprise of outcome x — a rare event (p(x) small) has high surprise, a common event has low surprise. The entropy is the expected surprise: the average value of -\log_2 p(X) under the distribution p. You do not yet know X; H(X) tells you, in bits, how surprised you expect to be once you see it.

Why \log_2 and not any other function of p: the base-2 logarithm makes the unit bits. One bit is the entropy of a fair coin, and it is also the information content of one yes/no answer. The choice of logarithm base is a choice of units, nothing more; \log_2 gives the right units for the rest of computer science.

Three quick sanity checks

Deterministic variable. If X takes a single value with probability 1, then -\sum_x p(x) \log_2 p(x) = -1 \cdot \log_2 1 = 0. Zero bits. No uncertainty.

Fair coin. If X takes two values with probability 1/2 each, then H(X) = -\tfrac{1}{2}\log_2\tfrac{1}{2} - \tfrac{1}{2}\log_2\tfrac{1}{2} = -\tfrac{1}{2}(-1) - \tfrac{1}{2}(-1) = 1. One bit.

Uniform over n outcomes. If X takes n values with probability 1/n each, then H(X) = -n \cdot \tfrac{1}{n}\log_2 \tfrac{1}{n} = \log_2 n. Why this is the maximum: for any distribution on n outcomes, Jensen's inequality applied to the concave function -x\log_2 x gives H(X) \leq \log_2 n, with equality iff the distribution is uniform. The uniform distribution spreads the probability as thinly as possible, so surprise is as uniform as possible.

A six-sided fair die has entropy \log_2 6 \approx 2.585 bits. A fair 52-card draw has entropy \log_2 52 \approx 5.700 bits. You need on average about 5.7 yes/no questions to guess the card.

Operational meaning — compression

Shannon entropy is not just an abstract measure of uncertainty. It has a sharp operational interpretation: H(X) is the minimum average number of bits per symbol you need to encode a long string drawn from p, in any lossless compression scheme.

This is the source-coding theorem. A message like "namaste namaste namaste" over a repetitive alphabet can be compressed far below its literal bit-length because the underlying p has low entropy. A genuinely random string over \{0, 1\} with p = 1/2 already has H = 1 bit per symbol and cannot be compressed further — every scheme that tries will fail on average.

So H(X) is simultaneously:

• The uncertainty of X before you see it.
• The information gained when you do see it.
• The minimum bits per symbol needed to losslessly store a long stream of draws from p.

All three numbers are the same. This triple-interpretation is why entropy is foundational and why it appears everywhere the word "information" does.

Binary entropy — the bump from 0 to 1

The most-used special case of Shannon entropy is the binary entropy function, which applies when X is a single Bernoulli variable with \Pr(X = 1) = p and \Pr(X = 0) = 1 - p:

This one-variable function comes up every time a bit is noisy, a qubit is measured, or a binary classifier is evaluated. Memorise its shape.

Three features worth internalising:

• H(0) = H(1) = 0. A coin that always lands heads has no uncertainty.
• H(1/2) = 1 bit. The fair coin is the maximally uncertain binary variable.
• Symmetry. H(p) = H(1 - p). Swapping the labels of the two outcomes does not change the uncertainty.

The concavity of H(p) has a name — it is the reason mixing two distributions never decreases entropy, a fact that will reappear in the quantum chapter as the concavity of von Neumann entropy.

Joint, conditional, and mutual information

One random variable is the baseline. Real communication involves pairs: sender X, receiver Y. Three quantities describe the pair.

Joint entropy

If X, Y are independent, p(x,y) = p(x)p(y) and a short calculation gives H(X, Y) = H(X) + H(Y):

Why the sums separate: the log of a product is a sum of logs, and the marginal sums \sum_y p(y) = 1 let the H(X) piece come out as a single factor. Independence makes total uncertainty additive — a sanity check that the formula agrees with intuition.

For correlated variables, H(X, Y) < H(X) + H(Y). The shortfall is the mutual information, which you will meet in a moment.

Conditional entropy

Reading the definition. H(Y | X = x) is the entropy of the conditional distribution p(y | x) — what the distribution of Y looks like after you learn that X took the value x. Averaging over all possible x (with weights p(x)) gives H(Y | X): on average, how much uncertainty about Y is left after observing X. The chain-rule identity H(Y|X) = H(X, Y) - H(X) is the definition's most useful form.

Two sanity checks: H(Y | X) = 0 if Y is a deterministic function of X (knowing X determines Y completely), and H(Y | X) = H(Y) if X, Y are independent (knowing X tells you nothing about Y). Between these extremes sits every real-world correlation.

Crucially, H(Y | X) \geq 0 — always. Classical conditional entropy cannot go negative. This is intuitive: knowing X can only reduce uncertainty about Y, never create it. The quantum analogue, as you will see in the next chapter, breaks this rule — and that break is entanglement.

Mutual information

Reading the definition. The first form reads as "total uncertainty if considered separately, minus total uncertainty when considered jointly." The shortfall is whatever redundancy the two variables share — i.e., how much information is held in common. The second form reads as "uncertainty of Y before knowing X, minus uncertainty of Y after knowing X." That reduction is the information X provides about Y.

The Venn picture is a literal accounting. Every identity between H, H(\cdot | \cdot), H(\cdot, \cdot), and I can be read off by treating the circles as sets and entropies as areas. This picture survives almost unchanged into the quantum chapter — with one shocking exception: for entangled states, the overlap can be larger than either circle. That's the thing negative conditional entropy formalises.

Channels and capacity

A communication channel takes an input symbol X \in \mathcal{X} and produces an output symbol Y \in \mathcal{Y} according to a conditional distribution p(y | x). The channel is noisy when Y is not a deterministic function of X. Two workhorse examples:

• Binary symmetric channel (BSC) with flip probability p. Input X \in \{0, 1\}. Output Y \in \{0, 1\}. Transition law: Y = X with probability 1 - p, Y = 1 - X with probability p. The same model as the classical repetition code channel.
• Binary erasure channel (BEC). Input X \in \{0, 1\}. Output Y \in \{0, 1, \mathtt{e}\} where \mathtt{e} means "erased". The receiver either sees the input exactly, or sees an explicit erasure symbol.

Reading the definition. For a fixed channel law p(y | x), the mutual information I(X; Y) depends on how you choose to distribute your input symbols. Channel capacity is what happens if you choose the best possible distribution — the one that lets the most information get through on average per channel use.

Shannon's noisy-channel theorem — the result that founded information theory

Shannon's 1948 masterpiece contains two theorems about capacity, which together are called the noisy-channel coding theorem:

1. Achievability. For any rate R < C, there exist codes that allow communication at rate R with arbitrarily small probability of decoding error, provided code length n is large enough.
2. Converse. For any rate R > C, every code has a decoding error probability bounded away from zero. Communication at rates exceeding capacity is fundamentally impossible.

The two-sided claim is what makes capacity a fundamental quantity, not just a handy definition. It says there is a sharp number C for every channel, below which everything works and above which nothing does. Shannon did not just define capacity — he proved capacity is the physical limit.

For a BSC with flip probability p, the capacity comes out to a clean formula:

where H(p) is the binary entropy. At p = 0, C = 1 bit per use (noiseless channel, full throughput). At p = 1/2, C = 0 (the channel is pure noise; no information gets through). At p = 0.01, C \approx 1 - 0.0808 \approx 0.919 bits per use — you can still push almost a full bit through a channel that flips one bit in a hundred, provided you use the right code.

The classical repetition code achieves only 1/n bits per use for n-fold repetition — vastly below capacity. Hamming, Reed-Solomon, LDPC, turbo, polar codes all approach C more efficiently. Modern 5G, Wi-Fi, and the Mars rover's downlink all use codes within fractions of a decibel of the Shannon limit.

Worked examples

Common confusions

• "Entropy is uncertainty; information is the opposite." Actually the same thing, in two framings. H(X) is simultaneously how uncertain you are about X before seeing it, and how much information you gain when you do see it. Before and after add to a constant, so they measure the same quantity.

• "Entropy is always a whole number of bits." No. H(1/10) \approx 0.469. The "bit" here is a unit, not an integer. You cannot literally transmit a fractional bit in one channel use, but over many uses the average bits per use can be any non-negative real.

• "Conditional entropy is the entropy of a conditional distribution." Close but not quite. H(Y | X = x) is the entropy of p(y | x) for a specific x. H(Y | X) is the average of H(Y | X = x) over all x, weighted by p(x). These are different objects — the first is a number depending on x, the second is a single number.

• "Mutual information can be negative if the variables are anticorrelated." No. Mutual information is always \geq 0. Anticorrelation is still correlation — it still reduces the joint entropy below the sum of marginals. The symbol I(X; Y) < 0 is a red flag for a calculation error.

• "Channel capacity is the rate of the best-known code." No, it is the rate of the best possible code. Capacity is a theoretical quantity defined from the channel alone, not from any code. That capacity is achievable is the content of Shannon's theorem; that known codes approach it is a separate engineering question.

• "Bigger alphabet means bigger entropy." Only if the probabilities support it. A uniform distribution over 1024 symbols has H = 10 bits, but a highly peaked distribution over the same 1024 symbols could have H < 1 bit. The alphabet size is the ceiling (H \leq \log_2 n), not the floor.

Going deeper

The asymptotic equipartition property (AEP)

The deepest single fact in Shannon's theory is the AEP. Fix a distribution p on \mathcal{X} and draw n independent samples x_1, \ldots, x_n. The typical set A_\epsilon^{(n)} is the set of sequences whose empirical probability p(x_1) \cdots p(x_n) = \prod_i p(x_i) satisfies

Three beautiful properties:

• Typical sequences are individually near-uniform in log-probability: each has probability roughly 2^{-nH(X)}.
• There are roughly 2^{nH(X)} typical sequences: the total probability weight is close to 1, and each piece weighs \approx 2^{-nH(X)}, so the count is \approx 2^{nH(X)}.
• Almost all the probability lives on typical sequences as n \to \infty: \Pr(A_\epsilon^{(n)}) \to 1 by the law of large numbers.

The AEP says: long samples from p look, in aggregate, like a uniform distribution on roughly 2^{nH(X)} equally likely sequences. This is why H(X) is the compression limit — you can enumerate the typical sequences in nH(X) bits, and handle the atypical remainder with a negligible fraction of the codebook. Proof of Shannon's source coding theorem is one AEP argument away.

The data-processing inequality

If X \to Y \to Z is a Markov chain (meaning Z depends on X only through Y), then

Why you cannot gain information by post-processing: Y is a bottleneck. Any function you compute from Y (including random functions like noisy channels) can only destroy information about X, not create new information. This inequality has a one-line proof from the chain rule for mutual information.

The data-processing inequality is used constantly in quantum information too — it is the classical skeleton of the quantum data-processing inequality that governs how much information a noisy quantum channel can preserve.

The Kullback-Leibler divergence

A finer information-theoretic quantity than entropy is the relative entropy (also called KL divergence):

It measures the "distance" between two distributions p and q — specifically, the number of extra bits you would waste per symbol if you built an optimal code for q but the true distribution is p. It is non-negative (D_{\text{KL}} \geq 0) with equality iff p = q, but it is not symmetric and does not satisfy the triangle inequality. It is the parent of many information-theoretic quantities: entropy, mutual information, and cross-entropy are all special cases of KL divergence.

The quantum analogue is the quantum relative entropy S(\rho \| \sigma) = \text{tr}(\rho \log \rho) - \text{tr}(\rho \log \sigma), which governs every inequality in quantum information theory.

A historical note

Claude Shannon's 1948 paper A Mathematical Theory of Communication created the field of information theory single-handedly. Before 1948, "communication" was engineering folklore — circuits and modulation schemes, with no mathematical framework tying performance to the channel's physics. Shannon introduced entropy, capacity, and the two theorems in one 55-page paper, and the field has been living inside that framework ever since.

The Indian connection is via C. R. Rao (Fisher information, Cramér-Rao bound, Rao distance) and Prasanta Mahalanobis (Mahalanobis distance, connections between information and statistics), both of whom developed parallel information-theoretic ideas in statistical inference around the same decades. Modern Indian work in information theory thrives at IISc, TIFR, and the IITs, with strong groups in coding theory, network information theory, and quantum information.

Where this leads next

• Von Neumann entropy — the quantum generalisation, where density operators replace probability distributions and every \log becomes a matrix log.
• Classical repetition codes — the simplest error-correcting code and its failure modes against quantum channels.
• Quantum mutual information — I(A; B) for density operators; always \geq 0, measures total correlations (classical plus quantum).
• Joint and conditional entropy — the quantum version, where S(A | B) can be negative and encodes entanglement.
• Channel capacity — Shannon's capacity for classical channels, and its several quantum analogues (classical, private, quantum capacities).

References

1. Claude E. Shannon, A Mathematical Theory of Communication (1948) — Bell System Technical Journal PDF.
2. Thomas M. Cover and Joy A. Thomas, Elements of Information Theory (2nd ed., 2006), Chapters 2–8 — Wiley.
3. David J. C. MacKay, Information Theory, Inference, and Learning Algorithms (2003), Chapters 2–10 — inference.org.uk/mackay/itila.
4. Wikipedia, Entropy (information theory) — definitions, properties, and channel-capacity formulas.
5. Wikipedia, Shannon's source coding theorem — formal statement and proof sketch of the AEP-based compression bound.
6. John Preskill, Lecture Notes on Quantum Computation, Ch. 10 (Quantum information theory) — theory.caltech.edu/~preskill/ph229.