Prerequisites & Notation

Before You Begin

This chapter builds on the entropy and typicality machinery from Chapters 1 and 3. The method of types provides a more refined, combinatorial approach to the same questions that typicality addresses probabilistically.

Discrete entropy, KL divergence, and mutual information (Ch 1)(Review ch01)
Self-check: Can you state the information inequality $D(P \| Q) \geq 0$ and recall when equality holds?
Strongly typical sets and the AEP (Ch 3)(Review ch03)
Self-check: Can you bound the size of the typical set $\mathcal{T}_\epsilon^{(n)}$ ?
Basic combinatorics: multinomial coefficients and Stirling's approximation
Self-check: Can you approximate $\binom{n}{k}$ using $2^{n H(k/n)}$ and explain why?
Convex optimization basics: KKT conditions, Lagrange multipliers
Self-check: Can you minimize a convex function subject to linear constraints using Lagrange multipliers?

Notation for This Chapter

Symbols introduced in this chapter. See the master notation table for global conventions.

Symbol	Meaning	Introduced
$\mathcal{X}$	Finite source alphabet with $\|\mathcal{X}\|$ elements	s01
$\hat{P}_{\mathbf{x}}$	Empirical distribution (type) of sequence $\mathbf{x} \in \mathcal{X}^n$	s01
$\mathcal{P}_n(\mathcal{X})$	Set of all types (empirical distributions) with denominator $n$ on alphabet $\mathcal{X}$	s01
$T_Q$	Type class: the set of all sequences in $\mathcal{X}^n$ with type $Q$	s01
$T_{V\|Q}$	Conditional type class: sequences $\mathbf{y}$ such that $(\mathbf{x}, \mathbf{y})$ has conditional type $V$	s01
$\doteq$	Exponential equality: $a_n \doteq 2^{nb}$ means $\lim_{n \to \infty} \frac{1}{n} \log a_n = b$	s01
$E_r(R)$	Random coding error exponent	s04
$E_{sp}(R)$	Sphere-packing error exponent	s04
$E_{ex}(R)$	Expurgated error exponent	s04
$R_{cr}$	Critical rate: the rate below which the random coding exponent is not tight	s04

← Ch 3 Types, Type Classes, and Their Properties