Chapter Summary

Chapter Summary

Key Points

• 1.

  The AEP: $-\frac{1}{n}\log P(\mathbf{X}) \to H(X)$ in probability. For i.i.d. sequences, the per-symbol log-probability concentrates around the entropy. This partitions $\mathcal{X}^n$ into a typical set of $\approx 2^{nH}$ likely sequences and an atypical set with negligible total probability.

• 2.

  Strong typicality controls per-symbol frequencies. A sequence is strongly typical if $|\hat{P}(a) - P(a)| \leq \epsilon P(a)$ for all $a$. Unlike weak typicality, strong typicality guarantees marginal consistency: jointly typical pairs have individually typical components.

• 3.

  The Joint Typicality Lemma: true pairs are typical, independent pairs are not. $\Pr((\mathbf{X}, \mathbf{Y}) \in \mathcal{T}_\epsilon^{(n)}) \to 1$ for true pairs, but $\Pr((\tilde{\mathbf{X}}, \mathbf{Y}) \in \mathcal{T}_\epsilon^{(n)}) \doteq 2^{-nI(X;Y)}$ for independent pairs. This exponential gap drives all coding theorems.

• 4.

  The Packing Lemma ensures reliable decoding. If $R < I(X;Y)$, no incorrect codeword is jointly typical with the output. This is the achievability engine for channel coding.

• 5.

  The Covering Lemma ensures source representation. If $R > I(X;\hat{X})$, at least one codeword is jointly typical with the source. This is the achievability engine for lossy source coding.

• 6.

  The method of types gives exact exponential bounds. Type class probability: $P^n(T_Q) \doteq 2^{-nD(Q\|P)}$. Type class size: $|T_Q| \doteq 2^{nH(Q)}$. Number of types: polynomial in $n$. Sanov's theorem governs large deviations.

• 7.

  The proof pattern is reusable. Random codebook + typicality decoding/encoding + packing/covering lemma = achievability proof. This architecture works for DMCs, Gaussian channels, MACs, broadcast channels, and beyond. By Part IV, you will construct these proofs for channels you have never seen.