Prerequisites & Notation

Before You Begin

This chapter builds on the transform methods and probability inequalities developed earlier in the book. Readers should be comfortable with moment generating functions and the Chernoff bound technique before proceeding.

Moment generating functions and their properties(Review fsp-ch09)
Self-check: Can you compute $M_X(t) = \mathbb{E}[e^{tX}]$ for a Gaussian and a Bernoulli RV?
Chernoff bound and exponential tilting(Review fsp-ch10)
Self-check: Can you derive $\mathbb{P}(X \geq a) \leq \inf_{t > 0} e^{-ta} M_X(t)$ ?
Weak law of large numbers and CLT(Review fsp-ch11)
Self-check: Do you understand that the sample mean concentrates around the true mean, and the CLT describes fluctuations at scale $1/\sqrt{n}$ ?
Kullback-Leibler divergence (basic definition)(Review ita-ch01)
Self-check: Can you compute $D(Q \| P)$ for two Bernoulli distributions?
Convex conjugates (Legendre transform)
Self-check: Given a convex function $f(t)$ , can you compute $f^*(x) = \sup_t \{tx - f(t)\}$ ?

Notation for This Chapter

Key symbols introduced or used throughout this chapter.

Symbol	Meaning	Introduced
$I(x)$	Rate function (Legendre-Fenchel transform of log-MGF)	s01
$\Lambda(\theta)$	Cumulant generating function: $\Lambda(\theta) = \log M_X(\theta)$	s01
$\Lambda^*(x)$	Fenchel-Legendre dual of $\Lambda$ : $\Lambda^*(x) = \sup_\theta \{\theta x - \Lambda(\theta)\}$	s01
$\hat{P}_n$	Empirical distribution (type) of $n$ i.i.d. samples	s02
$D(Q \\| P)$	Kullback-Leibler divergence from $P$ to $Q$	s02
$\sigma_{\mathrm{sg}}$	Sub-Gaussian parameter (proxy variance)	s03
$\bar{X}_n$	Sample mean: $\bar{X}_n = \frac{1}{n}\sum_{i=1}^n X_i$	s01
$E_r$	Error exponent (exponential decay rate of error probability)	s04

← Ch 19 Cramér's Theorem