Prerequisites & Notation

Before You Begin

This chapter assumes familiarity with discrete entropy and its properties from Chapter 1. The method of types (Chapter 4) provides the error exponent perspective but is not required for the main results.

Discrete entropy $H(X)$ and its properties (Ch 1)(Review ch01)
Self-check: Can you prove that $H(X) \leq \log |\mathcal{X}|$ with equality iff $X$ is uniform?
KL divergence $D(P \| Q)$ and the information inequality (Ch 1)(Review ch01)
Self-check: Can you state and prove $D(P \| Q) \geq 0$ ?
Conditional entropy and chain rule (Ch 1)(Review ch01)
Self-check: Can you write $H(X_1, \ldots, X_n) = \sum_{i=1}^n H(X_i | X_{i-1}, \ldots, X_1)$ ?
Basic probability: expectation, Jensen's inequality
Self-check: Can you apply Jensen's inequality to prove that $\mathbb{E}[\log f(X)] \leq \log \mathbb{E}[f(X)]$ for concave $\log$ ?

Notation for This Chapter

Symbols introduced in this chapter.

Symbol	Meaning	Introduced
$\mathcal{X}$	Source alphabet (finite, $\|\mathcal{X}\| = m$ )	s01
$\mathcal{D}$	Code alphabet (typically $\{0, 1\}$ for binary codes)	s01
$c : \mathcal{X} \to \mathcal{D}^*$	Source code: maps each source symbol to a codeword	s01
$\ell(x)$ or $\ell_i$	Codeword length for symbol $x$ (or $x_i$ )	s01
$L = \mathbb{E}[\ell(X)]$	Expected codeword length	s01
$L^*$	Minimum achievable expected codeword length	s02
$H_\infty$ or $H(\mathbb{X})$	Entropy rate of a stationary process $\{X_i\}$	s05
$\pi$	Stationary distribution of a Markov chain	s05
$c(\mathbf{x})$	Block code: maps length- $n$ sequences to binary strings	s01

← Ch 4 Prefix Codes and Kraft's Inequality