# Lecture 16: Data Compression and Shannon’s Noiseless Coding Theorem

Source: https://www.youtube.com/watch?v=4OpiI5NLjIE
Recap page: https://rapidrecap.app/video/4OpiI5NLjIE
Generated: 2025-12-17T16:36:50.88+00:00

---
## Quick Overview

Shannon's noiseless coding theorem establishes that the entropy H of a first-order source provides the absolute lower bound for the average length of any valid noiseless coding scheme, stating that the expected length is at least H times n minus little o of n, and that this bound is achievable up to the same lower-order term.

**Key Points:**
- Claude Shannon founded the field of information theory in 1948 in Building 2, laying the mathematical foundation for data compression.
- A first-order source is defined by an alphabet A (k symbols a1...ak) and a probability distribution p on A, operating like a k-sided unfair die generating IID samples.
- A valid coding function phi maps length n messages to variable-length 0,1 strings such that different messages map to different outputs, aiming to map frequent messages to shorter strings.
- The binary entropy function for a distribution p is defined as $H = -\sum_{i=1}^{k} p_i \log p_i$ (with log base 2), which quantifies the minimum per-symbol length achievable.
- Shannon's theorem states the expected length $L$ for any coding function $\phi$ is $L \ge Hn - o(n)$, and conversely, there exists a $\phi$ such that $L \le Hn + o(n)$.
- The uniform distribution ($p_i = 1/k$) maximizes the entropy, resulting in an entropy of $\log k$, corresponding to the naive encoding where no symbol is more frequent than others.
- The proof for the lower bound relies on analyzing $\epsilon$-typical sequences, showing that the expected length for these highly probable sequences is bounded by the entropy function using Stirling's approximation on the multinomial coefficient.

**Context:** The lecture introduces data compression by motivating the need for efficient communication using historical examples like telegram codebooks used to save money on costly messages, such as 'NBET' meaning 'captain is insane.' The core focus transitions to establishing the rigorous mathematical foundation for optimal data compression, centered around Claude Shannon's work from 1948, which defines a data source as a first-order source characterized by an alphabet and associated probabilities, similar to rolling a k-sided unfair die.

## Detailed Analysis

The lecture meticulously builds the case for Shannon's noiseless coding theorem by first defining the necessary components: a first-order source (IID samples from a biased die) and a valid coding function (a mapping to variable-length binary strings that is uniquely decodable). An example with a two-letter alphabet ($p_1=7/8, p_2=1/8$) demonstrated that a naive symbol-by-symbol encoding (expected length 2) could be improved upon (to 87/64). The optimal compression limit is then introduced via the binary entropy function, $H(p) = -\sum p_i \log p_i$. Shannon's theorem proves that $H$ is the optimal per-symbol length: any coding scheme has an expected length of at least $Hn - o(n)$, and an achievable scheme exists with an expected length of at most $Hn + o(n)$. The lower bound proof involves conditioning on the counts ($n_i$) of each symbol, using combinatorics (the multinomial coefficient $M$) and Stirling's approximation to show that $\log M \approx nH$. This is then generalized by arguing that this count-specific bound holds for $\epsilon$-typical sequences, which occur with probability approaching 1 as $n \to \infty$, linking the specific count case back to the general source distribution. The upper bound proof utilizes a block diagram strategy: for the highly probable $\epsilon$-typical sequences, the scheme encodes the signature ($n_1, \dots, n_k$) and then the specific sequence within that signature, achieving the $Hn + o(n)$ bound; for the rare non-typical sequences, the scheme can afford to use a trivial, linear-in-n encoding because their probability contribution to the total expected length becomes negligible ($o(n)$).

### Historical Context and Motivation

- Telegrams used codebooks like 'A-Z-K-H-E' for 'clean bill of health' to compress costly messages
- The lecture centers on proving Shannon's noiseless coding theorem for optimal compression.

### Definition of Data Source and Coding

- A first-order source is a k-sided unfair die generating IID samples
- A valid coding function $\phi$ maps length n messages to 0,1 strings such that different messages map to different outputs.

### Entropy and Optimal Limit

- Binary entropy $H(p) = -\sum p_i \log p_i$ is defined as the key measure for compression limits
- The uniform distribution maximizes entropy to $\log k$, corresponding to the naive encoding.

### Shannon's Noiseless Coding Theorem Statement

- Lower bound: Expected length $L \ge Hn - o(n)$ for any valid code $\phi$
- Upper bound: There exists $\phi$ such that $L \le Hn + o(n)$.

### Lower Bound Proof Intuition

- The proof relies on analyzing sequences whose empirical symbol counts ($n_i/n$) are $\epsilon$-close to the true probabilities ($p_i$) ($\epsilon$-typicality)
- For these typical sequences, the number of possibilities is bounded by a multinomial $M$, and $\log M$ approximates $nH$ via Stirling's formula.

### Upper Bound Proof Strategy

- The constructive proof uses a block diagram separating typical and non-typical sequences
- Encoding involves transmitting a 1-bit verdict (typical/not typical), followed by the signature $(n_1, \dots, n_k)$ (cost $k \log n$), and then the specific code, achieving the $Hn$ leading term for the highly probable typical case.