Formula & theorem reference

The Conditional Probability formula, applied to P(A\mid B) and to P(B\mid A) separately, gives two ways to write the same joint probability: P(A\text{ and }B) = P(A\mid B)\,P(B), \qquad P(A\text{ and }B) = P(B\mid A)\,P(A). Both right-hand sides equal the same quantity, so they equal each other: P(A\mid B)\,P(B) = P(B\mid A)\,P(A). Dividing both sides by P(B) (nonzero by hypothesis) isolates P(A\mid B): P(A\mid B) = \frac{P(B\mid A)\,P(A)}{P(B)}.

Direct, for the convex case. Let m = E[X]. Because g is convex, its graph lies on or above every one of its tangent lines — in particular the tangent line at the single point x=m: g(x) \geq g(m) + g'(m)(x-m) \quad \text{for all } x (if g isn't differentiable at m, any supporting line at that point works the same way). Take the expectation of both sides over X: E[g(X)] \geq E\big[g(m) + g'(m)(X-m)\big] = g(m) + g'(m)\big(E[X]-m\big). Since m = E[X], the term E[X]-m is exactly 0, so the right side collapses to g(m) = g(E[X]): E[g(X)] \geq g(E[X]). The concave case follows by applying this result to -g, which is convex whenever g is concave, and flipping the sign back.

Two separate arguments, one direct and one via Jensen's inequality.

Lower bound, direct. Every outcome x with p(x)>0 satisfies 0 < p(x) \leq 1, so \log_2 p(x) \leq 0 and therefore -p(x)\log_2 p(x) \geq 0. H(X) is a sum of these individually nonnegative terms, so H(X)\geq 0. Equality requires every term to vanish: for a term with p(x)>0, -p(x)\log_2 p(x)=0 forces \log_2 p(x)=0, i.e. p(x)=1. Since the probabilities sum to 1, at most one outcome can have p(x)=1 — so equality holds exactly when exactly one outcome carries all the probability.

Upper bound, via Jensen's inequality. Let S=\{x: p(x)>0\} be X's support, and write H(X) = \sum_{x\in S} p(x)\log_2\frac{1}{p(x)} = E\!\left[\log_2\frac1{p(X)}\right]. \log_2 is concave, so Jensen's inequality (applied to the concave case, exactly as previewed in Chapter 0) gives E\!\left[\log_2\frac{1}{p(X)}\right] \leq \log_2\!\left(E\!\left[\frac1{p(X)}\right]\right). Compute the inner expectation directly: E\!\left[\frac1{p(X)}\right] = \sum_{x\in S} p(x)\cdot\frac1{p(x)} = \sum_{x\in S} 1 = |S|. So H(X) \leq \log_2|S|. Since S is a subset of the full k-outcome alphabet, |S|\leq k, and \log_2 is increasing, so H(X) \leq \log_2|S| \leq \log_2 k. Jensen's inequality is an equality exactly when the quantity being averaged, 1/p(X), is constant over S — that is, p(x) is the same value for every x\in S, which (since those probabilities sum to 1) forces p(x)=1/|S| on S. Combined with |S|\leq k, the overall maximum \log_2 k is reached only when both inequalities are tight at once: |S|=k (every outcome has positive probability) and p(x)=1/k for each one — the uniform distribution over the full alphabet.

Direct, for the convex case. Let m = E[X]. Because g is convex, its graph lies on or above every one of its tangent lines — in particular the tangent line at the single point x=m: g(x) \geq g(m) + g'(m)(x-m) \quad \text{for all } x (if g isn't differentiable at m, any supporting line at that point works the same way). Take the expectation of both sides over X: E[g(X)] \geq E\big[g(m) + g'(m)(X-m)\big] = g(m) + g'(m)\big(E[X]-m\big). Since m = E[X], the term E[X]-m is exactly 0, so the right side collapses to g(m) = g(E[X]): E[g(X)] \geq g(E[X]). The concave case follows by applying this result to -g, which is convex whenever g is concave, and flipping the sign back.

Direct, via the chain rule for mutual information, applied twice.

Step 1 — a shared identity. For any three random variables, expanding the mutual information between X and the pair (Y,Z) two different ways gives I(X;Y) + I(X;Z\mid Y) \;=\; I(X;Y,Z) \;=\; I(X;Z) + I(X;Y\mid Z). \quad(1) This holds for every joint distribution; no Markov assumption is used yet.

Step 2 — the Markov hypothesis kills one term. For each fixed y, the hypothesis p(z\mid x,y)=p(z\mid y) says p(x,z\mid y) = p(x\mid y)\,p(z\mid y) — the conditional joint distribution of X and Z, given Y=y, factors into the product of its own conditional marginals. So every term inside that slice's mutual-information sum is \log_2\!\big[p(x,z\mid y)/(p(x\mid y)p(z\mid y))\big] = \log_2 1 = 0, giving I(X;Z\mid Y{=}y)=0 for every y, and therefore I(X;Z\mid Y)=0 once averaged over Y. Equation (1) collapses to I(X;Y) = I(X;Z) + I(X;Y\mid Z). Conditional mutual information is never negative, so I(X;Y\mid Z)\geq 0, giving I(X;Z) \leq I(X;Y).

Step 3 — the second bound, the same identity from Z's side. Expand I(Z;X,Y) instead of I(X;Y,Z): I(Z;Y) + I(Z;X\mid Y) \;=\; I(Z;X,Y) \;=\; I(Z;X) + I(Z;Y\mid X). I(Z;X\mid Y) = I(X;Z\mid Y) = 0 by the same Markov hypothesis (mutual information doesn't care about the order its two arguments are named in), so I(Z;Y) = I(Z;X) + I(Z;Y\mid X) \geq I(Z;X), i.e. I(X;Z) \leq I(Y;Z).

Direct, using Jensen's inequality applied to the concave function \log. Assume first that D(P||Q) is finite, i.e. Q(x) > 0 wherever P(x) > 0 — the infinite case is handled separately below.

Restrict every sum to the support of P (where P(x) > 0; those are the only terms that contribute) and flip the sign of the divergence by flipping the fraction inside the log: -D(P||Q) = \sum_{x:\,P(x)>0} P(x)\log\frac{Q(x)}{P(x)} = E_P\!\left[\log\frac{Q(X)}{P(X)}\right].

\log is concave, so Jensen's inequality (concave direction) applies to the random variable T = Q(X)/P(X), evaluated under P: E_P\!\left[\log\frac{Q(X)}{P(X)}\right] \;\leq\; \log\, E_P\!\left[\frac{Q(X)}{P(X)}\right].

Expand the right side directly from the definition of expectation: E_P\!\left[\frac{Q(X)}{P(X)}\right] = \sum_{x:\,P(x)>0} P(x)\cdot\frac{Q(x)}{P(x)} = \sum_{x:\,P(x)>0} Q(x) \;\leq\; \sum_{x} Q(x) = 1, since the middle sum only ranges over part of Q's alphabet and every term is non-negative. Because \log is increasing, \log of something \leq 1 is \leq \log 1 = 0. Chaining the two inequalities: -D(P||Q) = E_P\!\left[\log\frac{Q(X)}{P(X)}\right] \leq \log\, E_P\!\left[\frac{Q(X)}{P(X)}\right] \leq \log 1 = 0, so D(P||Q) \geq 0.

Equality. Two separate inequalities were chained above, and equality in the full statement forces both to be equalities individually.

• Jensen's inequality for a strictly concave function like \log is an equality only when the random variable being averaged is constant (Readiness, §4's own "equality only when there's nothing to average over"). So Q(x)/P(x) must equal one fixed constant c for every x with P(x) > 0.
• The second inequality, \sum_{x:P(x)>0} Q(x) \leq 1, is an equality only when Q places zero probability outside P's support — otherwise the sum strictly undercounts Q's total mass of 1.

Together: Q(x) = c\,P(x) on P's support, and Q has no mass elsewhere. Summing Q(x)=c\,P(x) over that support gives 1 = c\cdot 1, so c=1 — meaning Q(x)=P(x) everywhere P has support, and Q is 0 everywhere else, which is exactly where P is 0 too. So P=Q on all of \mathcal{X}.

The infinite case. If some x_0 has P(x_0)>0 but Q(x_0)=0, the sum defining D(P||Q) contains the term P(x_0)\log\big(P(x_0)/0\big), which diverges to +\infty since P(x_0) > 0 — consistent with the inequality D(P||Q)\geq 0 (infinity is certainly \geq 0), and equality is impossible here since P \neq Q at x_0 by assumption.

Both directions go through the same picture: a complete D-ary tree, every internal node with exactly D children, where a codeword of length l corresponds to a node at depth l, and a prefix code corresponds to a set of nodes none of which is an ancestor of another.

Necessity: a prefix code forces the inequality. Suppose codewords of lengths l_1, \ldots, l_k form a prefix code, and let l_{\max} = \max_i l_i. Extend the tree down to depth l_{\max}. The node for codeword i, sitting at depth l_i, has exactly D^{l_{\max}-l_i} descendants at depth l_{\max} (every one of its subtree's leaves at that depth). Because the code is prefix — no codeword's node is an ancestor of another's — these descendant sets, for i=1,\ldots,k, are pairwise disjoint subsets of the D^{l_{\max}} nodes that exist at depth l_{\max}. A union of disjoint subsets can't exceed the whole: \sum_{i=1}^{k} D^{l_{\max}-l_i} \leq D^{l_{\max}}. Dividing both sides by D^{l_{\max}} gives \sum_i D^{-l_i} \leq 1.

Sufficiency: the inequality forces a prefix code to exist. Now assume \sum_{i=1}^k D^{-l_i} \leq 1 and relabel so l_1 \leq l_2 \leq \cdots \leq l_k. Build the code one codeword at a time, in this order, always assigning codeword i to some as-yet-unclaimed node at depth l_i — one neither equal to, nor a descendant of, any node already assigned to an earlier codeword. It has to be shown such a node is always available.

At step i, each earlier codeword j<i sits at depth l_j \leq l_i and blocks exactly D^{l_i - l_j} of the D^{l_i} nodes at depth l_i (its own descendants there). So the number of nodes at depth l_i still free is at least D^{l_i} - \sum_{j<i} D^{l_i - l_j}. Divide by D^{l_i}: this is positive exactly when \sum_{j<i} D^{-l_j} < 1. And indeed \sum_{j<i} D^{-l_j} = \sum_{j=1}^{k} D^{-l_j} - \sum_{j \geq i} D^{-l_j} \leq 1 - D^{-l_i} < 1, using the hypothesis for the first inequality and D^{-l_i}>0 for the second. So a free node at depth l_i always exists — assign codeword i to any one of them (say, the leftmost).

By construction, codeword i's node is never a descendant of an earlier codeword's node (that's exactly what "free" excluded), and since every later codeword is likewise assigned only to nodes that aren't descendants of any node claimed so far, codeword i's node never becomes an ancestor of a later codeword's node either. So no node in the final set is an ancestor of another: the resulting code is a genuine prefix code with exactly the lengths l_1,\ldots,l_k.

Direct, via a counting argument on concatenated codewords (McMillan's own technique). Write S = \sum_{i=1}^k D^{-l_i}, and fix any positive integer n. Expanding the n-th power of S by multiplying out the sum with itself n times: S^n = \left(\sum_{i=1}^{k} D^{-l_i}\right)^{\!n} = \sum_{i_1=1}^{k} \sum_{i_2=1}^{k} \cdots \sum_{i_n=1}^{k} D^{-(l_{i_1}+l_{i_2}+\cdots+l_{i_n})}, a sum over every ordered n-tuple of codeword indices (i_1,\ldots,i_n).

Group the terms by their total length m = l_{i_1}+\cdots+l_{i_n}, which ranges from n\,l_{\min} to n\,l_{\max} (writing l_{\min}=\min_i l_i, l_{\max}=\max_i l_i). Let A_m be the number of n-tuples with total length exactly m: S^n = \sum_{m=n\,l_{\min}}^{n\,l_{\max}} A_m\, D^{-m}.

Each n-tuple (i_1,\ldots,i_n) names a length-n string of source symbols, and concatenating their codewords produces one specific D-ary string of length m. Because the code is uniquely decodable, this concatenation map is injective: two different n-tuples can never concatenate to the same D-ary string, or that string would decode two different ways. So A_m — the count of n-tuples landing at total length m — is at most the number of D-ary strings of length m that exist at all, which is D^m: A_m \leq D^m.

Substituting this bound in: S^n = \sum_{m=n\,l_{\min}}^{n\,l_{\max}} A_m\, D^{-m} \leq \sum_{m=n\,l_{\min}}^{n\,l_{\max}} D^m D^{-m} = \sum_{m=n\,l_{\min}}^{n\,l_{\max}} 1 = n(l_{\max}-l_{\min}) + 1 \leq n\, l_{\max}.

So S^n \leq n\, l_{\max} for every positive integer n. If S were strictly greater than 1, the left side would grow exponentially in n while the right side only grows linearly, and the inequality would fail for n large enough — a contradiction, since it was shown to hold for every n. The only way to avoid that contradiction is S \leq 1: \sum_{i=1}^{k} D^{-l_i} \leq 1.

Why this doesn't buy anything new. The Kraft inequality already showed this exact bound is both necessary and sufficient for a prefix code with lengths l_1,\ldots,l_k to exist. McMillan's inequality shows the same bound is also necessary for the strictly larger class of uniquely decodable codes. Combined, the two theorems say: whatever set of codeword lengths a uniquely decodable code can achieve, some prefix code achieves that exact same set of lengths too. Allowing non-prefix uniquely decodable codes never unlocks a shorter code than the best prefix code — restricting attention to prefix codes, which are decodable without lookahead, costs nothing in achievable length.

The bound is proved by turning it into an instance of Gibbs' inequality (relative entropy's non-negativity, 04-relative-entropy-and-cross-entropy §2), applied to the codeword lengths themselves rather than to two probability distributions in the usual sense.

Building a pseudo-distribution out of the lengths. Since C is uniquely decodable, the McMillan inequality applies to its lengths: \sum_x D^{-l(x)} \leq 1. Define q(x) := D^{-l(x)} \quad \text{for every outcome } x. Each q(x) is positive, and they sum to at most 1 — exactly the condition needed to run the Gibbs' inequality argument, whose own proof only ever used \sum_x Q(x) \leq 1, never that it equals 1 exactly (see that theorem's own "infinite case" step). So the same argument applies here even though \{q(x)\} is a genuine probability distribution only when C's lengths hit the Kraft bound with equality.

Rewriting the gap. Measuring entropy in D-ary units, H_D(X) := H(X)/\log_2 D = \sum_x p(x)\big({-\log_D p(x)}\big), the gap between expected length and this rescaled entropy is L - H_D(X) = \sum_x p(x)\,l(x) - \sum_x p(x)\big({-\log_D p(x)}\big) = \sum_x p(x)\Big(l(x) + \log_D p(x)\Big). Since l(x) = -\log_D D^{-l(x)} = -\log_D q(x), the bracketed term is -\log_D q(x) + \log_D p(x) = \log_D\!\dfrac{p(x)}{q(x)}, so L - H_D(X) = \sum_x p(x)\log_D\frac{p(x)}{q(x)}.

Applying Jensen to the log. This sum is non-negative by the same concave-Jensen step Gibbs' inequality itself runs: \log_D is concave, so for the random variable T = q(X)/p(X) evaluated under X's own distribution p, E_p\!\left[\log_D\frac{q(X)}{p(X)}\right] \leq \log_D E_p\!\left[\frac{q(X)}{p(X)}\right] = \log_D \sum_x p(x)\frac{q(x)}{p(x)} = \log_D \sum_x q(x) \leq \log_D 1 = 0, using \sum_x q(x)\leq 1 (McMillan) for the last step. The left side of that chain is exactly -\big(L-H_D(X)\big) (the same sum as above with the fraction flipped), so -(L - H_D(X)) \leq 0 \quad\Longleftrightarrow\quad L \geq H_D(X) = \frac{H(X)}{\log_2 D}.

Equality. Two inequalities were chained: the Jensen step, and \sum_x q(x) \leq 1. Equality throughout requires both individually tight.

• Jensen's inequality for the strictly concave \log_D is an equality only when T = q(X)/p(X) is constant across every outcome with p(x)>0 — say q(x) = c\,p(x) for some constant c.
• \sum_x q(x) \leq 1 is an equality only when C's lengths meet the Kraft bound exactly, \sum_x q(x) = 1.

Combining both: summing q(x)=c\,p(x) over all x gives 1 = c\cdot 1, so c=1, meaning q(x)=p(x) for every x — i.e. D^{-l(x)} = p(x), which rearranges to l(x) = -\log_D p(x). Since l(x) must be a positive integer, this equality case is only reachable when every -\log_D p(x) already happens to be a whole number; for any other source, L is strictly greater than H_D(X).

By induction on k, the alphabet size, built from two lemmas about what any optimal prefix code must already look like.

Setup. A binary prefix code corresponds to a binary tree with the symbols at the leaves and each codeword read off the root-to-leaf path. First: an optimal tree must be full — every internal node has exactly two children. If some internal node had only one child, deleting that node and attaching its child directly to the parent above shortens every codeword below it by one bit, strictly lowering E[l] — so an optimal tree could never contain such a node.

Lemma 1 (exchange argument: probability order matches length order). In an optimal code, p(x_i) > p(x_j) implies l(x_i) \leq l(x_j) — a strictly more probable symbol never sits at a strictly deeper leaf than a less probable one.

Suppose not: some optimal code has p(x_i) > p(x_j) but l(x_i) > l(x_j). Swap x_i and x_j's positions in the tree (exchange their codewords). The tree shape is unchanged, so the result is still a valid prefix code; only the expected length changes, by \Delta = \big(p(x_i)l(x_j) + p(x_j)l(x_i)\big) - \big(p(x_i)l(x_i) + p(x_j)l(x_j)\big) = \big(p(x_i)-p(x_j)\big)\big(l(x_j)-l(x_i)\big). The first factor is positive (p(x_i)>p(x_j)) and the second is negative (l(x_j)<l(x_i)), so \Delta < 0: the swap strictly lowers the expected length, contradicting optimality of the original code. So no such pair can exist in an optimal code.

A same-depth swap costs nothing by the identical computation: if l(x_i)=l(x_j), the second factor is 0 regardless of the probabilities, so \Delta=0 — relabeling two symbols at equal depth never changes E[l]. This fact is used below.

Lemma 2 (the two least-probable symbols can be siblings at maximum depth). Some optimal code has its two globally least-probable symbols as siblings (sharing a parent) at the tree's maximum depth.

Take any leaf at the tree's maximum depth d. Its sibling cannot be an internal node: an internal node's own children would sit at depth d+1, exceeding the tree's maximum depth d — impossible. So the sibling of any deepest leaf is itself a leaf at depth d; deepest leaves always come in sibling pairs. By Lemma 1's contrapositive, every leaf at depth d (the strictly largest depth present, when k>2) holds a probability no larger than any leaf at a shallower depth — the deepest level holds symbols from among the least probable in the whole distribution. Relabeling within that depth-d level costs nothing by Lemma 1's equal-depth case above, so the two globally least-probable symbols can always be swapped into one specific sibling pair at depth d without changing E[l].

Induction. k=1 is trivial (l=0, nothing to encode); k=2 is trivial (one bit each, and no shorter prefix code for two symbols exists). For k>2, assume the algorithm is optimal for every alphabet of size k-1. Let x,y be the two least-probable symbols of a k-symbol source. By Lemma 2, some optimal k-symbol code has x,y as siblings at maximum depth; merging them into one pseudo-symbol z with p(z)=p(x)+p(y) (deleting the shared parent's two leaves and relabeling that parent z) gives a valid (k-1)-symbol tree whose expected length is exactly E[l_k] - p(z) — each of x and y contributed one extra level of depth compared to z sitting at their parent's position, so removing that level removes exactly p(x)\cdot 1 + p(y)\cdot 1 = p(z) from the total. By the inductive hypothesis, the Huffman algorithm produces an optimal (k-1)-symbol tree for the distribution with z replacing x,y — and reattaching x,y as z's two children (exactly the algorithm's own next step, run in reverse) adds back precisely p(z) to any (k-1)-tree's expected length, optimal or not, by the identical accounting. Since the (k-1)-tree the algorithm builds is optimal among (k-1)-symbol trees, and the +p(z) adjustment applies uniformly, the reattached k-symbol tree is optimal among k-symbol trees too. The algorithm's first move — merge the two least-probable symbols — is exactly the move this argument requires, so induction carries the optimality claim through every step it takes.

The two forms say the same thing. Take logs of the defining inequality for A_\varepsilon^{(n)} and divide by -n (which reverses both inequalities): 2^{-n(H+\varepsilon)} \le p(x^n) \le 2^{-n(H-\varepsilon)} \;\iff\; -n(H+\varepsilon) \le \log_2 p(x^n) \le -n(H-\varepsilon) \;\iff\; H-\varepsilon \le -\tfrac1n\log_2 p(x^n) \le H+\varepsilon. So x^n \in A_\varepsilon^{(n)} exactly when \big|-\tfrac1n\log_2 p(x^n) - H\big| \le \varepsilon — membership in the typical set and closeness of -\tfrac1n\log_2 p(x^n) to H(X) are the same statement, not two separate claims to prove.

Convergence in probability. Because the X_i are independent, p(X^n) = \prod_i p(X_i), so -\frac1n\log_2 p(X^n) = \frac1n\sum_{i=1}^n \big(-\log_2 p(X_i)\big) = \overline{Y}_n, the sample average of the i.i.d. random variables Y_i = -\log_2 p(X_i). Each Y_i has mean E[Y_i] = \sum_x p(x)\big(-\log_2 p(x)\big) = H(X) by the definition of entropy, and finite variance \sigma^2 (the alphabet is finite, so Y_i takes finitely many values). The weak law of large numbers applies directly to \overline Y_n: for every \varepsilon>0, P\big(|\overline Y_n - H(X)| \ge \varepsilon\big) \to 0 \quad \text{as } n \to \infty, which is exactly -\tfrac1n\log_2 p(X^n) \to H(X) in probability — and, by the equivalence just shown, exactly P(X^n \in A_\varepsilon^{(n)}) \to 1. Pick N large enough that this probability exceeds 1-\varepsilon.

Size bounds. For the upper bound, probabilities over the whole space sum to at most 1, and every sequence in A_\varepsilon^{(n)} has probability at least 2^{-n(H+\varepsilon)}: 1 \;\ge\; \sum_{x^n \in A_\varepsilon^{(n)}} p(x^n) \;\ge\; \big|A_\varepsilon^{(n)}\big|\cdot 2^{-n(H+\varepsilon)} \;\implies\; \big|A_\varepsilon^{(n)}\big| \le 2^{n(H+\varepsilon)}. For the lower bound, take n\ge N so P(A_\varepsilon^{(n)})>1-\varepsilon; every sequence in A_\varepsilon^{(n)} also has probability at most 2^{-n(H-\varepsilon)}, so 1-\varepsilon \;<\; P\big(A_\varepsilon^{(n)}\big) \;=\; \sum_{x^n \in A_\varepsilon^{(n)}} p(x^n) \;\le\; \big|A_\varepsilon^{(n)}\big|\cdot 2^{-n(H-\varepsilon)} \;\implies\; \big|A_\varepsilon^{(n)}\big| > (1-\varepsilon)\,2^{n(H-\varepsilon)}.

\bar X_n has mean \mu and, since the X_i are independent, variance \sigma^2/n (chapter 10's own sum-of-independent-variables rule, applied n times). Applying Chebyshev's inequality to \bar X_n with k=\varepsilon\sqrt n/\sigma gives P\big(|\bar X_n-\mu|\ge\varepsilon\big) \le \frac{\sigma^2}{n\varepsilon^2}. The right side shrinks to 0 as n\to\infty, for any fixed \varepsilon>0, which is exactly the convergence the law claims.

Achievability. Fix R>H(X) and \delta>0. Let \varepsilon = \tfrac12(R-H(X)) > 0, so that H(X)+\varepsilon = \tfrac12(H(X)+R) < R strictly, since R > H(X). By the AEP, choose n_0 large enough that both P\big(X^n \in A_\varepsilon^{(n)}\big) > 1-\delta \quad\text{and}\quad \big|A_\varepsilon^{(n)}\big| \le 2^{n(H(X)+\varepsilon)} < 2^{nR}. Build the code by setting S_n = A_\varepsilon^{(n)}: since |S_n| \le 2^{nR}, every sequence in S_n gets its own length-\lceil nR\rceil codeword, with room to spare because the inequality above is strict. The decoder errs exactly when X^n \notin S_n = A_\varepsilon^{(n)}, which happens with probability P(X^n\notin A_\varepsilon^{(n)}) < \delta by construction. This is the whole idea in one sentence: don't try to code every possible sequence, only the (comparatively few) typical ones, and accept that the rare atypical draw fails — a failure whose probability the AEP already drove below \delta.

Converse. Fix R<H(X), and let \varepsilon = \tfrac12(H(X)-R)>0, so H(X)-\varepsilon-R = \varepsilon > 0. Take any rate-R code with encodable set S_n, |S_n|\le 2^{nR}. Split S_n's probability mass by whether each sequence is typical: P(X^n \in S_n) = P\big(X^n \in S_n \cap A_\varepsilon^{(n)}\big) + P\big(X^n \in S_n \setminus A_\varepsilon^{(n)}\big). Every sequence in A_\varepsilon^{(n)} has probability at most 2^{-n(H(X)-\varepsilon)} (the AEP's defining bound), so the first term is at most |S_n|\cdot 2^{-n(H(X)-\varepsilon)} \le 2^{nR}\cdot 2^{-n(H(X)-\varepsilon)} = 2^{-n(H(X)-\varepsilon-R)} = 2^{-n\varepsilon}. The second term is at most P(X^n\notin A_\varepsilon^{(n)}), which the AEP already sends to 0. So P(X^n \in S_n) \le 2^{-n\varepsilon} + P\big(X^n \notin A_\varepsilon^{(n)}\big) \;\longrightarrow\; 0 \quad\text{as } n\to\infty, regardless of which set S_n of size \le 2^{nR} the code chose — a set that small simply cannot own enough probability, typical or not. Since the probability of decoding correctly vanishes, the probability of error, 1-P(X^n\in S_n), approaches 1.

Direct, by the same Jensen's-inequality argument that proved Gibbs' inequality for discrete distributions (Ch. 4), replayed here in integral form for two densities instead of two pmfs.

The key algebraic fact. Because g is Gaussian, \log_2 g(x) is an explicit quadratic function of x: \log_2 g(x) = -\tfrac12\log_2(2\pi\sigma^2) - \frac{(x-\mu)^2}{2\sigma^2\ln 2}. This quadratic depends on x only through (x-\mu)^2 — so its expectation under any distribution that shares G's mean and variance is the same number it would be under G itself. Concretely, since X has mean \mu and variance \sigma^2 by hypothesis, E_f[(X-\mu)^2]=\sigma^2, so E_f[\log_2 g(X)] = -\tfrac12\log_2(2\pi\sigma^2) - \frac{\sigma^2}{2\sigma^2\ln 2} = -\tfrac12\log_2(2\pi\sigma^2) - \tfrac12\log_2 e = -\tfrac12\log_2(2\pi e\sigma^2) = -h(G). So -\int f(x)\log_2 g(x)\,dx = h(G) — an identity that holds regardless of f's actual shape, as long as f's mean and variance match G's.

Chaining to the entropy gap. Using that identity in place of h(G), h(G)-h(X) = -\int f(x)\log_2 g(x)\,dx - \left(-\int f(x)\log_2 f(x)\,dx\right) = \int f(x)\log_2\frac{f(x)}{g(x)}\,dx. This is exactly the same expression Gibbs' inequality bounds below by zero for two discrete distributions — the proof there never actually used that the arguments were finite pmfs, only that they were nonnegative and integrated (summed) to 1, so it transfers verbatim. Restricting to f's support and flipping the fraction, -\!\int_{f>0}\! f(x)\log_2\frac{g(x)}{f(x)}\,dx = -E_f\!\left[\log_2\frac{g(X)}{f(X)}\right] \geq -\log_2 E_f\!\left[\frac{g(X)}{f(X)}\right] by Jensen's inequality (concave \log_2, sign flipped by the leading minus). The expectation on the right expands directly: E_f\!\left[\frac{g(X)}{f(X)}\right] = \int_{f>0} f(x)\cdot\frac{g(x)}{f(x)}\,dx = \int_{f>0} g(x)\,dx \leq \int_{-\infty}^{\infty} g(x)\,dx = 1, since the middle integral covers only part of g's support and g\geq0 everywhere. So E_f[g(X)/f(X)]\leq1, and since \log_2 is increasing, -\log_2(\text{something}\leq1)\geq -\log_2 1 = 0. Chaining: h(G)-h(X) = \int f(x)\log_2\frac{f(x)}{g(x)}\,dx \geq 0, so h(X)\leq h(G).

Equality. Two inequalities were chained, and equality in the combined statement forces both individually. Jensen's inequality for the strictly concave \log_2 is tight only when the quantity being averaged, g(X)/f(X), is constant on f's support — call that constant c. The second inequality, \int_{f>0}g(x)\,dx\leq 1, is tight only when g places no mass outside f's support. Together, g(x)=c\,f(x) everywhere f>0, and g=0 elsewhere; integrating g=cf over f's support gives 1=c\cdot1, so c=1 and g=f on that support — and since g is 0 exactly where f is 0 too, f=g everywhere. So equality holds if and only if X is Gaussian.

Achievability. Fix R<C and \delta>0; write p^*(x) for a capacity-achieving input distribution and let p(y)=\sum_x p^*(x)p(y|x) be the resulting output distribution, so I(X;Y)=C for this joint law. Let \varepsilon = (C-R)/6 > 0.

Codebook. Generate M=2^{nR} codewords X^n(1),\ldots,X^n(M) independently, each with its n coordinates drawn i.i.d.\ from p^*(x). This random codebook is revealed to both encoder and decoder before any message is sent — the randomness is a tool for the existence argument below, not something repeated per transmission.

Decoder. Define the jointly typical set, the pair-sequence analog of Chapter 8's typical set A_\varepsilon^{(n)}: A_\varepsilon^{(n)} = \Big\{(x^n,y^n): \big|{-\tfrac1n\log_2 p(x^n)-H(X)}\big|\le\varepsilon,\ \big|{-\tfrac1n\log_2 p(y^n)-H(Y)}\big|\le\varepsilon,\ \big|{-\tfrac1n\log_2 p(x^n,y^n)-H(X,Y)}\big|\le\varepsilon\Big\}. On receiving y^n, the decoder outputs the unique i with (x^n(i),y^n)\in A_\varepsilon^{(n)}; if no such i exists, or more than one does, it declares an error. This is the same law-of-large-numbers machinery Chapter 8 used on a single sequence, applied here to the pair (X^n,Y^n): -\tfrac1n\log_2 p(X^n,Y^n) is a sample average of i.i.d.
terms with mean H(X,Y), and likewise for each marginal, so all three defining bounds hold with probability \to 1 by the same weak-law argument typical-set-aep already proves for one sequence at a time.

Error analysis. By symmetry (every codeword is drawn from the same distribution, and the channel acts identically on each), assume message 1 was sent; average error probability equals P(\text{error}\mid \text{message }1). An error happens only if (X^n(1),Y^n)\notin A_\varepsilon^{(n)} (call this E_0) or some j\neq 1 has (X^n(j),Y^n)\in A_\varepsilon^{(n)} (call this E_j). By the union bound, P(\text{error}) \le P(E_0) + \sum_{j=2}^M P(E_j). The joint AEP sends P(E_0)\to 0 as n\to\infty; fix n large enough that P(E_0)<\delta/2.

For j\neq 1, X^n(j) was drawn independently of both X^n(1) and the channel noise, so it is independent of Y^n — but it shares Y^n's marginal-consistent distribution only through p^*(x), not through having actually caused Y^n. For any two sequences \tilde X^n\sim p^*(x)^n and \tilde Y^n\sim p(y)^n drawn independently of each other, P\big((\tilde X^n,\tilde Y^n)\in A_\varepsilon^{(n)}\big) = \!\!\sum_{(x^n,y^n)\in A_\varepsilon^{(n)}}\!\! p(x^n)p(y^n) \le \big|A_\varepsilon^{(n)}\big|\cdot 2^{-n(H(X)-\varepsilon)}\cdot 2^{-n(H(Y)-\varepsilon)}, using that every pair in A_\varepsilon^{(n)} has p(x^n)\le 2^{-n(H(X)-\varepsilon)} and p(y^n)\le 2^{-n(H(Y)-\varepsilon)} by the first two defining bounds. The same counting step Chapter 8 used to bound a typical set's size bounds this one: \big|A_\varepsilon^{(n)}\big| \le 2^{n(H(X,Y)+\varepsilon)}, since every pair in it has joint probability at least 2^{-n(H(X,Y)+\varepsilon)} and probabilities sum to at most 1. Combining, P\big((\tilde X^n,\tilde Y^n)\in A_\varepsilon^{(n)}\big) \le 2^{n(H(X,Y)+\varepsilon)}\cdot 2^{-n(H(X)+H(Y)-2\varepsilon)} = 2^{-n(H(X)+H(Y)-H(X,Y)-3\varepsilon)} = 2^{-n(I(X;Y)-3\varepsilon)}, using I(X;Y)=H(X)+H(Y)-H(X,Y), one of the two equivalent definitions from Chapter 3. Since X^n(j) and Y^n are exactly such an independent pair and I(X;Y)=C here, P(E_j)\le 2^{-n(C-3\varepsilon)} for every j, so \sum_{j=2}^M P(E_j) \le (M-1)\cdot 2^{-n(C-3\varepsilon)} < 2^{nR}\cdot 2^{-n(C-3\varepsilon)} = 2^{-n(C-R-3\varepsilon)}. By the choice \varepsilon=(C-R)/6, C-R-3\varepsilon = (C-R)/2>0 (strictly positive because R<C), so this sum is 2^{-n(C-R)/2}\to 0 as n\to\infty; take n large enough that it is also below \delta/2.

Existence. For n large enough, both terms are below \delta/2, so P(\text{error})<\delta — but this is the error probability averaged over the random codebook, not one particular code's. Averaging over a collection of numbers that are all \ge 0 and whose average is below \delta means at least one of them is itself below \delta: at least one actual codebook in the ensemble has average error probability P_e^{(n)}<\delta. That codebook, with the jointly-typical decoder just described, is a genuine (2^{nR},n) code. Since this holds for every \delta>0 once n is large enough, a sequence of such codes has P_e^{(n)}\to 0, which is exactly what "R is achievable" means.

Converse (sketch). Suppose R>C and fix any (2^{nR},n) code with an arbitrary decoder, i.e.\ a partition of \mathcal Y^n into M=2^{nR} decision regions D_1,\ldots,D_M. Whatever input distribution this particular code's codewords happen to induce, the resulting mutual information is at most C by the very definition of capacity as a maximum over input distributions — so replace C below by this code's own I(X;Y)\le C; the bound only gets easier to violate. For the decoder to have small error on codeword i, D_i must capture nearly all of the probability mass the channel actually sends codeword i's output into — a set of roughly 2^{nH(Y|X)} sequences, by the same AEP-style counting used above, now applied to Y^n conditioned on X^n=f(i). Chapter 8's own single-sequence AEP, applied to the output process Y^n on its own, also says the outputs actually worth allocating any decision region to at all number at most about 2^{n(H(Y)+\varepsilon)}. Fitting M essentially disjoint regions of size \approx 2^{nH(Y|X)} inside a space of size \approx 2^{n(H(Y)+\varepsilon)} forces M\cdot 2^{n(H(Y|X)-\varepsilon)} \lesssim 2^{n(H(Y)+\varepsilon)} \quad\Longrightarrow\quad M \lesssim 2^{n(I(X;Y)+2\varepsilon)} \le 2^{n(C+2\varepsilon)}. Since M=2^{nR} with R>C, this packing bound is violated for n large enough and \varepsilon small enough — the M regions cannot all be close to disjoint copies of their codeword's typical output set, so a non-negligible fraction of the space is claimed by more than one message's decision region (or left to none), and every codeword whose region has been crowded out contributes actual error. This argument correctly shows P_e^{(n)} cannot be pushed to 0; turning "the regions don't fit" into a precise, code-independent lower bound on P_e^{(n)} — the full strong converse, P_e^{(n)}\to 1 — takes one more tool, Fano's inequality, previewed later in this course.

Sizing. H has m rows, so the code has n-k=m and n=2^m-1 (the number of distinct nonzero binary strings of length m), giving k=2^m-1-m.

Minimum distance. The minimum distance of a linear code equals the smallest number of linearly dependent columns of its parity-check matrix. No two columns of H are equal (they're the 2^m-1 distinct nonzero strings, each appearing once) and no column is zero, so no single column and no pair of columns is dependent — ruling out d_{min}\leq2. Any three DISTINCT nonzero length-m binary strings can sum to zero (e.g. for m=3: columns 001,010,011 sum to 000), so d_{min}=3 exactly.

Error correction/detection. By the general detect/correct bound (Chapter 12, Section 2), a code with d_{min}=3 corrects any error of weight up to \lfloor(d_{min}-1)/2\rfloor=1 and detects any error of weight up to d_{min}-1=2 — precisely single-error-correction, double-error-detection.

Hamming bound. Around each codeword, a "sphere" of radius t (every vector within Hamming distance t) contains \sum_{i=0}^{t}\binom{n}{i} vectors. Since d\geq2t+1, any two distinct codewords' spheres are disjoint (a vector within t of two different codewords would put those codewords within 2t<d of each other, contradicting the minimum distance). M disjoint spheres, each of that size, must fit inside the full space of 2^n vectors, giving the bound.

Singleton bound. Take any code \mathcal{C} with M codewords and minimum distance d. Deleting any d-1 fixed coordinate positions from every codeword cannot make two DISTINCT codewords collide — if it did, the two original codewords would already agree everywhere outside those d-1 positions, differing in at most d-1 places, contradicting d_{min}=d. So the M shortened codewords, now length n-d+1, are still all distinct, and there are only 2^{n-d+1} possible vectors of that length to be distinct among.

Plotkin bound. Sum the Hamming distance between every pair of the M codewords two ways. Directly, each of the \binom{M}2 pairs contributes at least d, for a total of at least d\binom{M}2. Counted column by column instead: in column j, if w_j codewords have a 1 there, that column contributes w_j(M-w_j) to the pairwise-distance sum (each of the w_j ones pairs with each of the M-w_j zeros), maximized at M^2/4 when w_j=M/2 — so the total across all n columns is at most nM^2/4. Combining, d\binom{M}2 \leq nM^2/4, which rearranges (using 2d>n) to the stated bound.

Gilbert-Varshamov bound. A greedy argument: build a code one codeword at a time, always adding a new vector at distance \geq d from every codeword chosen so far. Adding a codeword "forbids" every vector within distance d-1 of it — a sphere of size \sum_{i=0}^{d-1}\binom{n}{i} — from ever being chosen later. As long as already-chosen codewords' forbidden spheres haven't covered the entire space of 2^n vectors, another codeword can still be added. This process is guaranteed to reach at least M=2^n/\sum_{i=0}^{d-1}\binom{n}{i} codewords before every vector is forbidden.

Monotonicity, direct. If \delta_1 \leq \delta_2, every p(\hat x\mid x) satisfying E[d]\leq\delta_1 also satisfies E[d]\leq\delta_2 — the feasible set only grows as \delta increases. A minimum taken over a larger set can't exceed a minimum taken over a smaller one, so R(\delta_2)\leq R(\delta_1). Non-negativity is immediate: I(X;\hat X) is a mutual information, never negative for any joint law.

Convexity, by mixing two optimal schemes. Let \delta_1,\delta_2\geq0 and \lambda\in[0,1]; write \delta_\lambda = \lambda\delta_1 + (1-\lambda)\delta_2. Let p_1(\hat x\mid x) and p_2(\hat x\mid x) achieve R(\delta_1) and R(\delta_2) exactly (a minimum over a compact set of distributions with a continuous objective is attained). Introduce an auxiliary switch \Theta\in\{1,2\}, independent of X, with P(\Theta=1)=\lambda, and define \hat X by: given \Theta=\theta, generate \hat X from p_\theta(\hat x\mid x). This is a genuine conditional law p_\lambda(\hat x\mid x) = \lambda p_1(\hat x\mid x) + (1-\lambda)p_2(\hat x\mid x), so it's a legal competitor in the definition of R(\delta_\lambda) once its distortion and mutual information are checked.

Distortion is linear in the mixture: E[d(X,\hat X)] = \lambda E_1[d(X,\hat X)] + (1-\lambda)E_2[d(X,\hat X)] \leq \lambda\delta_1 + (1-\lambda)\delta_2 = \delta_\lambda, directly from how \hat X was generated.

Mutual information needs one chain-rule step, derived here rather than assumed. For any three random variables A,B,C, expanding I(A;B,C)=H(A)-H(A\mid B,C) and writing H(A\mid B,C) = H(A\mid B) - I(A;C\mid B) (the definition of conditional mutual information, Chapter 3) gives I(A;B,C) = I(A;B) + I(A;C\mid B). Apply this with A=X, B=\Theta, C=\hat X: I(X;\Theta,\hat X) = I(X;\Theta) + I(X;\hat X\mid \Theta). \Theta is independent of X by construction, so I(X;\Theta)=0. And I(X;\hat X\mid\Theta) = \lambda I(X;\hat X\mid\Theta=1) + (1-\lambda) I(X;\hat X\mid\Theta=2) by the definition of conditional mutual information as an average over \Theta's own distribution — and conditioned on \Theta=\theta, the pair (X,\hat X) has exactly the joint law p(x)p_\theta(\hat x\mid x), so I(X;\hat X\mid\Theta=\theta) is exactly the mutual information p_\theta achieves, namely R(\delta_\theta). So I(X;\Theta,\hat X) = \lambda R(\delta_1) + (1-\lambda)R(\delta_2).

Apply the same chain-rule identity once more with the roles of \Theta and \hat X swapped, A=X, B=\hat X, C=\Theta: I(X;\hat X,\Theta) = I(X;\hat X) + I(X;\Theta\mid\hat X). Conditional mutual information is never negative (Gibbs' inequality applied conditionally, exactly as it proves ordinary mutual information is never negative), so I(X;\hat X) \leq I(X;\hat X,\Theta). Chaining the two displayed identities, I(X;\hat X) \;\leq\; I(X;\Theta,\hat X) \;=\; \lambda R(\delta_1) + (1-\lambda)R(\delta_2). So p_\lambda(\hat x\mid x) achieves distortion at most \delta_\lambda with mutual information at most \lambda R(\delta_1)+(1-\lambda)R(\delta_2) — and since R(\delta_\lambda) is the minimum mutual information over every conditional law meeting the \delta_\lambda distortion budget, R(\delta_\lambda) \;\leq\; I(X;\hat X) \;\leq\; \lambda R(\delta_1) + (1-\lambda) R(\delta_2), which is exactly the definition of R being convex.

Converse: no scheme beats the bound. Fix any length-n scheme — encoder f_n, decoder g_n, M=2^{nR} indices — and let \hat X^n = g_n(f_n(X^n)) be its reproduction, with per-symbol distortions \delta_i = E[d(X_i,\hat X_i)] and average \bar\delta = \frac1n\sum_i\delta_i. Since \hat X^n is a deterministic function of X^n taking at most M values, I(X^n;\hat X^n) \leq H(\hat X^n) \leq \log_2 M = nR (mutual information never exceeds the entropy of either argument, and entropy never exceeds the log of the alphabet size — both Chapter 2/3 facts). Separately, because the X_i are i.i.d., I(X^n;\hat X^n) = \sum_{i=1}^n H(X_i) - H(X^n\mid\hat X^n) \;\geq\; \sum_{i=1}^n \big[H(X_i) - H(X_i\mid \hat X_i)\big] = \sum_{i=1}^n I(X_i;\hat X_i), using H(X^n)=\sum_i H(X_i) for independent X_i (Chapter 3) and H(X^n\mid\hat X^n) \leq \sum_i H(X_i\mid\hat X_i), which follows because conditioning on more variables can only lower entropy (Chapter 3): H(X_i\mid\hat X^n, X^{i-1}) \leq H(X_i\mid\hat X_i) term by term, since the left side conditions on a superset of \{\hat X_i\}. Each term I(X_i;\hat X_i) is, by definition, at least R(\delta_i) — no conditional law achieving distortion \delta_i on X_i can beat the minimum R(\delta_i). So nR \;\geq\; I(X^n;\hat X^n) \;\geq\; \sum_{i=1}^n R(\delta_i) \;\geq\; n\cdot R(\bar\delta) \;\geq\; n\cdot R(\delta) where the second-to-last step is Jensen's inequality applied to the convex function R over the average \bar\delta=\frac1n\sum_i\delta_i, and the last step uses R non-increasing together with \bar\delta \leq \delta (the scheme's own guarantee). Dividing by n: R \geq R(\delta) — any scheme holding average distortion at or below \delta must run at rate at least R(\delta).

Achievability, sketch. The construction mirrors the noisy-channel coding theorem's random-codebook argument, with the roles of encoder and decoder reversed. Fix R>R(\delta) and let p^*(\hat x\mid x) achieve R(\delta') for some \delta'<\delta close enough that R(\delta')<R still holds (possible since R(\delta) is continuous and R>R(\delta) leaves room). Generate a codebook of 2^{nR} reproduction sequences \hat X^n(1),\ldots,\hat X^n(2^{nR}), each drawn i.i.d.\ from the marginal p^*(\hat x) = \sum_x p(x)p^*(\hat x\mid x) induced by p^*. Given a source block x^n, the encoder searches the codebook for any index j with (x^n,\hat X^n(j)) jointly typical under the joint law p(x)p^*(\hat x\mid x) (the same jointly typical set built for the noisy-channel coding theorem). A covering argument — the AEP-driven counterpart of that theorem's packing argument, showing a random codebook of size 2^{nR} almost surely contains a jointly typical partner for x^n whenever R exceeds I(X;\hat X)=R(\delta') — makes this search succeed with probability approaching 1 as n\to\infty. Whenever it succeeds, joint typicality itself guarantees the empirical joint distribution of (x^n,\hat X^n(j)) lands close to p(x)p^*(\hat x\mid x), whose expected distortion is \delta'; the rare failure case is handled by falling back to any fixed reproduction sequence, contributing a vanishing correction to the average distortion as its probability goes to 0. Averaged over the random codebook, the expected distortion approaches \delta'<\delta, so — by the same "the average over a collection is achieved by at least one member" step used for the noisy-channel coding theorem — some particular codebook achieves average distortion at most \delta+\varepsilon for n large enough, at rate R.

Direct, chaining three facts already established about entropy: perfect secrecy's own definition, the chain rule for entropy applied to M and K conditioned throughout on C, and the fact that conditioning never increases entropy.

Step 1 — perfect secrecy converts to an entropy equality. I(M;C)=0 is, by mutual information's own definition, exactly H(M) - H(M\mid C) = 0. So perfect secrecy gives H(M) = H(M\mid C).

Step 2 — bound H(M\mid C) by H(K\mid C). Because M is a deterministic function of (C,K) (decryption always recovers M exactly, with no randomness left over), H(M\mid C, K) = 0: once both the ciphertext and the key are known, there's nothing left to be uncertain about. The chain rule for entropy, applied to M and K with everything conditioned on C, reads H(M,K\mid C) = H(K\mid C) + H(M\mid K,C) = H(K\mid C) + 0 = H(K\mid C). Entropy of a pair is never smaller than the entropy of either half alone — dropping K from the pair (M,K) can only lose information, never create uncertainty about M that wasn't already there — so H(M\mid C) \leq H(M,K\mid C). Combined with the line above, H(M\mid C) \leq H(K\mid C).

Step 3 — conditioning never increases entropy. This was proved in Chapter 3: for any two random variables, H(K\mid C) \leq H(K), since learning C can only narrow down K's possibilities on average, never widen them.

Chain the three steps together: H(M) \;=\; H(M\mid C) \;\leq\; H(K\mid C) \;\leq\; H(K). So H(M) \leq H(K).

Direct, by the method of Lagrange multipliers, worked through for the single-constraint case m=1 with f_1(X)=X — a fixed mean E[X]=\mu — since every extra constraint only adds one more multiplier to the same argument without changing its shape.

Setting up the Lagrangian. Maximize H(p) = -\sum_i p_i\ln p_i (natural log for calculus; switching to \log_2 at the end only rescales every p_i's exponent by a constant, it doesn't move where the maximum sits) subject to \sum_i p_i = 1 and \sum_i p_i x_i = \mu. Introduce one multiplier per constraint: \mathcal{L}(p,\lambda_0,\lambda_1) = -\sum_i p_i\ln p_i - \lambda_0\Big(\sum_i p_i - 1\Big) - \lambda_1\Big(\sum_i p_i x_i - \mu\Big).

Solving for the stationary point. Treating each p_i as a free variable and differentiating, \frac{\partial \mathcal{L}}{\partial p_i} = -\ln p_i - 1 - \lambda_0 - \lambda_1 x_i = 0 \quad\Longrightarrow\quad p_i = \exp(-1-\lambda_0)\exp(-\lambda_1 x_i). The first factor doesn't depend on i, so writing C = \exp(-1-\lambda_0) gives exactly the claimed exponential form, p_i = C\exp(-\lambda_1 x_i), with C playing the role of 1/Z(\lambda_1) once normalization pins it down. \lambda_1 itself is then whatever value makes \sum_i p_i x_i=\mu hold — a one-dimensional equation in \lambda_1 that always has a unique solution once \mu lies strictly between the smallest and largest x_i, since \sum_i p_i x_i moves continuously and monotonically in \lambda_1 from one extreme to the other as \lambda_1 ranges over the reals.

Why this stationary point is the maximum, not just A critical point. H(p) = -\sum_i p_i\ln p_i is a strictly concave function of p on the probability simplex — it's a sum of the strictly concave single-variable functions -p_i\ln p_i, and a sum of concave functions is concave — while both constraints are linear in p. Maximizing a strictly concave function over a set cut out by linear constraints has at most one stationary point, and that point is automatically the global maximum over the whole constraint set, not merely a local one. So the p_i = C\exp(-\lambda_1 x_i) found above isn't one candidate among several; it's the unique entropy-maximizing distribution consistent with the mean constraint.

General m constraints. Nothing above used that there was only one constraint beyond normalization — repeating the same differentiation with m multipliers \lambda_1,\dots,\lambda_m, one per constraint function f_j, produces \partial\mathcal{L}/\partial p_i = -\ln p_i - 1 - \lambda_0 - \sum_j\lambda_j f_j(x_i) = 0, giving exactly p_i \propto \exp(-\sum_j \lambda_j f_j(x_i)) — the general form stated above, by the identical argument.

Direct, via the Cauchy–Schwarz inequality applied to the estimator and the score function S(X;\theta) = \partial_\theta \ln f(X;\theta).

Two identities the score function satisfies. Since f(\cdot;\theta) integrates (or sums) to 1 for every \theta, differentiating both sides with respect to \theta and exchanging the order of differentiation and integration (the regularity condition doing its job) gives 0 = \partial_\theta \int f(x;\theta)\,dx = \int \partial_\theta f(x;\theta)\,dx = \int f(x;\theta)\,\partial_\theta \ln f(x;\theta)\,dx = E[S(X;\theta)], using \partial_\theta \ln f = \partial_\theta f / f. So the score has mean zero, which makes \operatorname{Var}(S) = E[S^2] = I(\theta) exactly the Fisher information from the definition above — no separate computation needed.

A second identity comes from unbiasedness. Differentiating E[\hat\theta] = \int \hat\theta(x) f(x;\theta)\,dx = \theta with respect to \theta, again exchanging differentiation and integration, 1 = \int \hat\theta(x)\,\partial_\theta f(x;\theta)\,dx = \int \hat\theta(x)\,f(x;\theta)\,S(x;\theta)\,dx = E\big[\hat\theta\, S(X;\theta)\big]. Since E[S]=0, this says \operatorname{Cov}(\hat\theta, S) = E[\hat\theta S] - E[\hat\theta]E[S] = E[\hat\theta S] = 1.

Applying Cauchy–Schwarz. The Cauchy–Schwarz inequality, met earlier for ordinary vectors, holds equally for the inner product \langle U,V\rangle = E[UV] on mean-zero random variables (Cov(\hat\theta,S) is exactly this inner product once \hat\theta is centered, since S already has mean zero): \operatorname{Cov}(\hat\theta,S)^2 \leq \operatorname{Var}(\hat\theta)\operatorname{Var}(S). Substituting the two identities just derived, 1^2 \leq \operatorname{Var}(\hat\theta)\cdot I(\theta) \quad\Longrightarrow\quad \operatorname{Var}(\hat\theta) \geq \frac{1}{I(\theta)}.

A concrete instance: estimating a Gaussian mean. Let X_1,\dots,X_n be i.i.d. N(\theta,\sigma^2) with \sigma^2 known. For one observation, \ln f(x;\theta) = -\ln(\sigma\sqrt{2\pi}) - (x-\theta)^2/(2\sigma^2), so S_1(x;\theta) = \partial_\theta \ln f = (x-\theta)/\sigma^2 and I_1(\theta) = E[S_1^2] = \operatorname{Var}(X)/\sigma^4 = \sigma^2/\sigma^4 = 1/\sigma^2. By additivity, I(\theta) = n/\sigma^2, so the bound says \operatorname{Var}(\hat\theta) \geq \sigma^2/n for any unbiased estimator built from these n observations. The sample mean \bar X = \frac1n\sum_i X_i is unbiased (E[\bar X]=\theta) with \operatorname{Var}(\bar X) = \sigma^2/n exactly — the bound holds with equality. No unbiased estimator of a Gaussian mean can ever beat the sample mean's variance; the sample mean is Cramér–Rao efficient.

Direct, via the chain rule for mutual information, applied twice.

Step 1 — a shared identity. For any three random variables, expanding the mutual information between X and the pair (Y,Z) two different ways gives I(X;Y) + I(X;Z\mid Y) \;=\; I(X;Y,Z) \;=\; I(X;Z) + I(X;Y\mid Z). \quad(1) This holds for every joint distribution; no Markov assumption is used yet.

Step 2 — the Markov hypothesis kills one term. For each fixed y, the hypothesis p(z\mid x,y)=p(z\mid y) says p(x,z\mid y) = p(x\mid y)\,p(z\mid y) — the conditional joint distribution of X and Z, given Y=y, factors into the product of its own conditional marginals. So every term inside that slice's mutual-information sum is \log_2\!\big[p(x,z\mid y)/(p(x\mid y)p(z\mid y))\big] = \log_2 1 = 0, giving I(X;Z\mid Y{=}y)=0 for every y, and therefore I(X;Z\mid Y)=0 once averaged over Y. Equation (1) collapses to I(X;Y) = I(X;Z) + I(X;Y\mid Z). Conditional mutual information is never negative, so I(X;Y\mid Z)\geq 0, giving I(X;Z) \leq I(X;Y).

Step 3 — the second bound, the same identity from Z's side. Expand I(Z;X,Y) instead of I(X;Y,Z): I(Z;Y) + I(Z;X\mid Y) \;=\; I(Z;X,Y) \;=\; I(Z;X) + I(Z;Y\mid X). I(Z;X\mid Y) = I(X;Z\mid Y) = 0 by the same Markov hypothesis (mutual information doesn't care about the order its two arguments are named in), so I(Z;Y) = I(Z;X) + I(Z;Y\mid X) \geq I(Z;X), i.e. I(X;Z) \leq I(Y;Z).

Direct, via the entropy of the error indicator and two applications of the chain rule for entropy.

Set up the error indicator. Let E = \mathbf{1}\{\hat{X}\neq X\}, a Bernoulli(P_e) random variable that is completely determined once both X and Y are known — \hat X=g(Y) is a fixed function of Y, so (X,Y) pins down both \hat X and whether it disagrees with X. That gives H(E\mid X,Y) = 0: there's nothing left to describe once X and Y are both known.

Expand H(E,X\mid Y) two ways. The chain rule for entropy applies just as well to a conditional joint entropy as an unconditional one: H(E,X\mid Y) = H(X\mid Y) + H(E\mid X,Y) = H(X\mid Y) + 0 = H(X\mid Y), grouping X first. Grouping E first instead, H(E,X\mid Y) = H(E\mid Y) + H(X\mid E,Y). Joint entropy doesn't care which variable is named first, so both expansions equal the same quantity H(E,X\mid Y). Setting them equal: H(X\mid Y) = H(E\mid Y) + H(X\mid E,Y). \quad(1)

Bound the first term. Conditioning never increases entropy (Chapter 3), so H(E\mid Y) \leq H(E). And H(E) is exactly the binary entropy of a Bernoulli(P_e) variable: H(E) = h(P_e).

Bound the second term. Split the conditioning on E itself: H(X\mid E,Y) = P(E=0)\,H(X\mid E=0,Y) + P(E=1)\,H(X\mid E=1,Y). When E=0, the estimator is correct — X = \hat X = g(Y) is a fixed, known function of Y, so there is no remaining uncertainty at all: H(X\mid E=0,Y)=0. When E=1, all that's known is that X is some value other than \hat X — one of the remaining M-1 symbols — so X's conditional distribution is supported on a set of size at most M-1, and the entropy of any distribution on at most M-1 outcomes is at most \log_2(M-1) (the entropy upper bound from Chapter 2). So H(X\mid E,Y) \leq (1-P_e)\cdot 0 + P_e\cdot\log_2(M-1) = P_e\log_2(M-1).

Combine. Substituting both bounds into (1): H(X\mid Y) \leq h(P_e) + P_e\log_2(M-1).

The simplified form. Since h(P_e)\leq 1 bit for every P_e\in[0,1] (the entropy bound applied to a two-outcome variable), replacing h(P_e) with 1 can only weaken the inequality, giving H(X\mid Y) \leq 1 + P_e\log_2(M-1), which rearranges — whenever \log_2(M-1) > 0, i.e. M \geq 3 — to P_e \geq \big(H(X\mid Y)-1\big)/\log_2(M-1).

A two-step reduction: first cut a distribution over any number of outcomes down to a distribution over just two, then settle the two-outcome case directly. Work in nats throughout (write D, d for natural-log divergence) and convert to bits only in the last line, since dividing both sides of a true inequality by the same positive constant \ln 2 preserves it.

Step 1 — reduce to two outcomes. Let A = \{x : P(x)\geq Q(x)\} and B = \mathcal{X}\setminus A, and set p = P(A), q=Q(A). Every term in A has P(x)\geq Q(x) and every term in B has P(x)<Q(x), so \|P-Q\|_1 = \sum_{x\in A}\big(P(x)-Q(x)\big) + \sum_{x\in B}\big(Q(x)-P(x)\big) = (p-q) + \big((1-q)-(1-p)\big) = 2(p-q). A is, by construction, the single set on which P and Q disagree the most in one direction, so p \geq q.

Grouping D(P||Q)'s defining sum into its A-part and B-part and applying the log-sum inequality to each — itself a direct consequence of the convexity of t\log t (Readiness §3–4) — gives \sum_{x\in A} P(x)\log\frac{P(x)}{Q(x)} \geq p\log\frac{p}{q}, \qquad \sum_{x\in B} P(x)\log\frac{P(x)}{Q(x)} \geq (1-p)\log\frac{1-p}{1-q}, the same "merging outcomes can only reduce a logarithmic gap" fact used informally throughout this chapter. Adding the two: D(P||Q) \;\geq\; p\ln\frac{p}{q} + (1-p)\ln\frac{1-p}{1-q} \;=:\; d(p||q), the ordinary binary relative entropy between Bernoulli(p) and Bernoulli(q). The problem is now purely about two numbers, p\geq q in [0,1].

Step 2 — the binary case. Fix p and treat d(p||q) as a function of q\in(0,1). Differentiating, \frac{d}{dq}\,d(p||q) = -\frac{p}{q} + \frac{1-p}{1-q} = \frac{q-p}{q(1-q)}. Since d(p||p)=0, the fundamental theorem of calculus gives, for q\leq p, d(p||q) = \int_q^p \frac{p-t}{t(1-t)}\,dt. Every t\in(0,1) satisfies t(1-t)\leq \tfrac14 (completing the square: t(1-t) = \tfrac14-(t-\tfrac12)^2), so 1/[t(1-t)]\geq 4 throughout the range of integration, and (p-t)\geq 0 there too since t\leq p. So d(p||q) \;\geq\; \int_q^p 4(p-t)\,dt \;=\; 4\left[\,pt - \tfrac{t^2}{2}\,\right]_{t=q}^{p} \;=\; 2(p-q)^2.

Combine. Chaining Steps 1 and 2, and using p-q = \tfrac12\|P-Q\|_1 from Step 1: D(P||Q) \;\geq\; d(p||q) \;\geq\; 2(p-q)^2 \;=\; 2\left(\tfrac12\|P-Q\|_1\right)^2 = \tfrac12\|P-Q\|_1^2, the nats form of the theorem. Dividing both sides by \ln 2 converts D on the left to bits and produces the stated constant 1/(2\ln 2) on the right.

Achievability. Fix R>H(X) and \delta>0. Let \varepsilon = \tfrac12(R-H(X)) > 0, so that H(X)+\varepsilon = \tfrac12(H(X)+R) < R strictly, since R > H(X). By the AEP, choose n_0 large enough that both P\big(X^n \in A_\varepsilon^{(n)}\big) > 1-\delta \quad\text{and}\quad \big|A_\varepsilon^{(n)}\big| \le 2^{n(H(X)+\varepsilon)} < 2^{nR}. Build the code by setting S_n = A_\varepsilon^{(n)}: since |S_n| \le 2^{nR}, every sequence in S_n gets its own length-\lceil nR\rceil codeword, with room to spare because the inequality above is strict. The decoder errs exactly when X^n \notin S_n = A_\varepsilon^{(n)}, which happens with probability P(X^n\notin A_\varepsilon^{(n)}) < \delta by construction. This is the whole idea in one sentence: don't try to code every possible sequence, only the (comparatively few) typical ones, and accept that the rare atypical draw fails — a failure whose probability the AEP already drove below \delta.

Converse. Fix R<H(X), and let \varepsilon = \tfrac12(H(X)-R)>0, so H(X)-\varepsilon-R = \varepsilon > 0. Take any rate-R code with encodable set S_n, |S_n|\le 2^{nR}. Split S_n's probability mass by whether each sequence is typical: P(X^n \in S_n) = P\big(X^n \in S_n \cap A_\varepsilon^{(n)}\big) + P\big(X^n \in S_n \setminus A_\varepsilon^{(n)}\big). Every sequence in A_\varepsilon^{(n)} has probability at most 2^{-n(H(X)-\varepsilon)} (the AEP's defining bound), so the first term is at most |S_n|\cdot 2^{-n(H(X)-\varepsilon)} \le 2^{nR}\cdot 2^{-n(H(X)-\varepsilon)} = 2^{-n(H(X)-\varepsilon-R)} = 2^{-n\varepsilon}. The second term is at most P(X^n\notin A_\varepsilon^{(n)}), which the AEP already sends to 0. So P(X^n \in S_n) \le 2^{-n\varepsilon} + P\big(X^n \notin A_\varepsilon^{(n)}\big) \;\longrightarrow\; 0 \quad\text{as } n\to\infty, regardless of which set S_n of size \le 2^{nR} the code chose — a set that small simply cannot own enough probability, typical or not. Since the probability of decoding correctly vanishes, the probability of error, 1-P(X^n\in S_n), approaches 1.

Achievability. Fix R<C and \delta>0; write p^*(x) for a capacity-achieving input distribution and let p(y)=\sum_x p^*(x)p(y|x) be the resulting output distribution, so I(X;Y)=C for this joint law. Let \varepsilon = (C-R)/6 > 0.

Codebook. Generate M=2^{nR} codewords X^n(1),\ldots,X^n(M) independently, each with its n coordinates drawn i.i.d.\ from p^*(x). This random codebook is revealed to both encoder and decoder before any message is sent — the randomness is a tool for the existence argument below, not something repeated per transmission.

Decoder. Define the jointly typical set, the pair-sequence analog of Chapter 8's typical set A_\varepsilon^{(n)}: A_\varepsilon^{(n)} = \Big\{(x^n,y^n): \big|{-\tfrac1n\log_2 p(x^n)-H(X)}\big|\le\varepsilon,\ \big|{-\tfrac1n\log_2 p(y^n)-H(Y)}\big|\le\varepsilon,\ \big|{-\tfrac1n\log_2 p(x^n,y^n)-H(X,Y)}\big|\le\varepsilon\Big\}. On receiving y^n, the decoder outputs the unique i with (x^n(i),y^n)\in A_\varepsilon^{(n)}; if no such i exists, or more than one does, it declares an error. This is the same law-of-large-numbers machinery Chapter 8 used on a single sequence, applied here to the pair (X^n,Y^n): -\tfrac1n\log_2 p(X^n,Y^n) is a sample average of i.i.d.
terms with mean H(X,Y), and likewise for each marginal, so all three defining bounds hold with probability \to 1 by the same weak-law argument typical-set-aep already proves for one sequence at a time.

Error analysis. By symmetry (every codeword is drawn from the same distribution, and the channel acts identically on each), assume message 1 was sent; average error probability equals P(\text{error}\mid \text{message }1). An error happens only if (X^n(1),Y^n)\notin A_\varepsilon^{(n)} (call this E_0) or some j\neq 1 has (X^n(j),Y^n)\in A_\varepsilon^{(n)} (call this E_j). By the union bound, P(\text{error}) \le P(E_0) + \sum_{j=2}^M P(E_j). The joint AEP sends P(E_0)\to 0 as n\to\infty; fix n large enough that P(E_0)<\delta/2.

For j\neq 1, X^n(j) was drawn independently of both X^n(1) and the channel noise, so it is independent of Y^n — but it shares Y^n's marginal-consistent distribution only through p^*(x), not through having actually caused Y^n. For any two sequences \tilde X^n\sim p^*(x)^n and \tilde Y^n\sim p(y)^n drawn independently of each other, P\big((\tilde X^n,\tilde Y^n)\in A_\varepsilon^{(n)}\big) = \!\!\sum_{(x^n,y^n)\in A_\varepsilon^{(n)}}\!\! p(x^n)p(y^n) \le \big|A_\varepsilon^{(n)}\big|\cdot 2^{-n(H(X)-\varepsilon)}\cdot 2^{-n(H(Y)-\varepsilon)}, using that every pair in A_\varepsilon^{(n)} has p(x^n)\le 2^{-n(H(X)-\varepsilon)} and p(y^n)\le 2^{-n(H(Y)-\varepsilon)} by the first two defining bounds. The same counting step Chapter 8 used to bound a typical set's size bounds this one: \big|A_\varepsilon^{(n)}\big| \le 2^{n(H(X,Y)+\varepsilon)}, since every pair in it has joint probability at least 2^{-n(H(X,Y)+\varepsilon)} and probabilities sum to at most 1. Combining, P\big((\tilde X^n,\tilde Y^n)\in A_\varepsilon^{(n)}\big) \le 2^{n(H(X,Y)+\varepsilon)}\cdot 2^{-n(H(X)+H(Y)-2\varepsilon)} = 2^{-n(H(X)+H(Y)-H(X,Y)-3\varepsilon)} = 2^{-n(I(X;Y)-3\varepsilon)}, using I(X;Y)=H(X)+H(Y)-H(X,Y), one of the two equivalent definitions from Chapter 3. Since X^n(j) and Y^n are exactly such an independent pair and I(X;Y)=C here, P(E_j)\le 2^{-n(C-3\varepsilon)} for every j, so \sum_{j=2}^M P(E_j) \le (M-1)\cdot 2^{-n(C-3\varepsilon)} < 2^{nR}\cdot 2^{-n(C-3\varepsilon)} = 2^{-n(C-R-3\varepsilon)}. By the choice \varepsilon=(C-R)/6, C-R-3\varepsilon = (C-R)/2>0 (strictly positive because R<C), so this sum is 2^{-n(C-R)/2}\to 0 as n\to\infty; take n large enough that it is also below \delta/2.

Existence. For n large enough, both terms are below \delta/2, so P(\text{error})<\delta — but this is the error probability averaged over the random codebook, not one particular code's. Averaging over a collection of numbers that are all \ge 0 and whose average is below \delta means at least one of them is itself below \delta: at least one actual codebook in the ensemble has average error probability P_e^{(n)}<\delta. That codebook, with the jointly-typical decoder just described, is a genuine (2^{nR},n) code. Since this holds for every \delta>0 once n is large enough, a sequence of such codes has P_e^{(n)}\to 0, which is exactly what "R is achievable" means.

Converse (sketch). Suppose R>C and fix any (2^{nR},n) code with an arbitrary decoder, i.e.\ a partition of \mathcal Y^n into M=2^{nR} decision regions D_1,\ldots,D_M. Whatever input distribution this particular code's codewords happen to induce, the resulting mutual information is at most C by the very definition of capacity as a maximum over input distributions — so replace C below by this code's own I(X;Y)\le C; the bound only gets easier to violate. For the decoder to have small error on codeword i, D_i must capture nearly all of the probability mass the channel actually sends codeword i's output into — a set of roughly 2^{nH(Y|X)} sequences, by the same AEP-style counting used above, now applied to Y^n conditioned on X^n=f(i). Chapter 8's own single-sequence AEP, applied to the output process Y^n on its own, also says the outputs actually worth allocating any decision region to at all number at most about 2^{n(H(Y)+\varepsilon)}. Fitting M essentially disjoint regions of size \approx 2^{nH(Y|X)} inside a space of size \approx 2^{n(H(Y)+\varepsilon)} forces M\cdot 2^{n(H(Y|X)-\varepsilon)} \lesssim 2^{n(H(Y)+\varepsilon)} \quad\Longrightarrow\quad M \lesssim 2^{n(I(X;Y)+2\varepsilon)} \le 2^{n(C+2\varepsilon)}. Since M=2^{nR} with R>C, this packing bound is violated for n large enough and \varepsilon small enough — the M regions cannot all be close to disjoint copies of their codeword's typical output set, so a non-negligible fraction of the space is claimed by more than one message's decision region (or left to none), and every codeword whose region has been crowded out contributes actual error. This argument correctly shows P_e^{(n)} cannot be pushed to 0; turning "the regions don't fit" into a precise, code-independent lower bound on P_e^{(n)} — the full strong converse, P_e^{(n)}\to 1 — takes one more tool, Fano's inequality, previewed later in this course.