Prerequisites & Notation

Before You Begin

This chapter develops the central technical machinery for proving coding theorems. We assume solid understanding of discrete and continuous information measures from Chapters 1-2.

Entropy, mutual information, KL divergence (Chapter 1)(Review ita/ch01)
Self-check: Can you state Fano's inequality and the data processing inequality?
Differential entropy and the Gaussian maximum entropy property (Chapter 2)(Review ita/ch02)
Self-check: Can you compute the differential entropy of a Gaussian vector?
Weak law of large numbers
Self-check: Can you state the WLLN and explain what convergence in probability means?
Union bound and basic combinatorics
Self-check: Can you bound $\Pr(A_1 \cup \cdots \cup A_M)$ using the union bound?
Empirical distribution (histogram) of a sequence
Self-check: Given a binary sequence $0110100$ , can you compute the empirical frequency of each symbol?

Notation for This Chapter

New notation for typicality. Prior notation from Chapters 1-2 carries over.

Symbol	Meaning	Introduced
$X^n = (X_1, \ldots, X_n)$	A sequence of $n$ random variables	s01
$\mathbf{x} = (x_1, \ldots, x_n)$	A realization (specific sequence)	s01
$\mathcal{T}_\epsilon^{(n)}(X)$	Strongly typical set for distribution $P_X$	s02
$\hat{P}_{\mathbf{x}}(a)$	Empirical distribution (type) of sequence $\mathbf{x}$ : fraction of positions with value $a$	s02
$\dot{=}$	Equality to first order in the exponent: $f(n) \dot{=} g(n)$ means $\frac{1}{n}\log\frac{f(n)}{g(n)} \to 0$	s01
$T_Q$	Type class: set of all sequences with empirical distribution $Q$	s05

← Ch 2 The Asymptotic Equipartition Property (AEP)