Chapter Summary

Chapter Summary

Key Points

• 1.

  The method of types as a refined lens. Every sequence $\mathbf{x} \in \mathcal{X}^n$ has a type (empirical distribution) $\hat{P}_{\mathbf{x}}$, and the type class $T_Q$ contains all sequences sharing type $Q$. Three fundamental facts drive the entire chapter: (1) the number of types is polynomial $(n+1)^{|\mathcal{X}|}$, (2) the type class size is $|T_Q| \doteq 2^{nH(Q)}$, and (3) the probability of a type class under i.i.d. source $P$ is $P^n(T_Q) \doteq 2^{-nD(Q \| P)}$. These replace the softer bounds of typicality with exponentially tight estimates.

• 2.

  Sanov's theorem: geometry on the simplex. The probability that the empirical distribution falls in a set $\mathcal{E}$ decays as $2^{-nD^*(\mathcal{E} \| P)}$, where $D^*$ is the minimum KL divergence from $\mathcal{E}$ to the truth $P$. This converts probability questions into optimization problems on the probability simplex — finding the closest distribution in $\mathcal{E}$ to $P$ in the KL sense.

• 3.

  Source coding exponent: redundancy buys reliability. Coding a DMS at rate $R > H(P)$ gives error probability decaying as $2^{-nE_s(R)}$ where $E_s(R) = \min_{Q : H(Q) \geq R} D(Q \| P)$. The exponent grows with redundancy $R - H(P)$ and is zero at the Shannon limit.

• 4.

  Channel coding exponents: the reliability function. For a DMC at rate $R < C$, the random coding exponent $E_r(R)$ is achievable and equals the sphere-packing converse $E_{sp}(R)$ for $R \geq R_{cr}$. Below the critical rate, the expurgated exponent $E_{ex}(R)$ improves upon $E_r$. At capacity, all exponents are zero — the boundary of reliable communication.

• 5.

  Theory vs. practice. Error exponents characterize the ultimate reliability of unstructured codes at fixed rates. Practical codes (LDPC, polar, turbo) trade error exponent for decoding complexity, achieving capacity through iterative decoding at rates approaching $C$ rather than through exponential reliability at fixed $R < C$. For short-blocklength regimes (5G URLLC), the finite-blocklength framework (Chapter 26) provides tighter characterizations.