Information has a budget.

A probability model says what may happen. Information theory asks what that model permits: compact description, learning from data, reliable communication through noise. Logs are base 2, so the unit is the bit.

Caltech EE/Ma/CS 126a · Fall 2022 notes · 6 slides · under 3 minutes

The spine

Full explainer

Slide 2 of 6 · Q: How does the subject split?

Two laws, two kinds of work.

Compression · source coding

$$H(X) = -\sum_{x} p(x)\log_2 p(x)$$

Average surprise of the source. The source coding theorem makes it the description-length limit.

Communication · channel coding

$$C = \max_{p(x)}\, I(X;Y)$$

Mutual information maximized over the input distribution. This is the channel's capacity.

CarefulThe two limits share units, not a proof.

The ledger

Full explainer

Slide 3 of 6 · Q: What is the basic accounting?

Uncertainty you can add up.

Self-information · halving p adds one bit

$$\imath(x) = -\log_2 p(x)$$

Chain rule

$$H(X,Y) = H(X) + H(Y\mid X)$$

Mutual information · two equal readings

$$I(X;Y) = H(X) - H(X\mid Y) = D_{\mathrm{KL}}\!\big(p(x,y)\,\|\,p(x)p(y)\big)$$

Uncertainty about X that Y removes, and the divergence from the joint law to independence.

The bridge

Full explainer

Slide 4 of 6 · Q: Why does entropy set the limit?

The A-E-P turns averages into counts.

Asymptotic Equipartition Property

$$-\tfrac{1}{n}\log_2 p(X_1,\dots,X_n) \;\xrightarrow{\;p\;}\; H(X)$$

The typical set carries the mass

$$|A_\varepsilon^{(n)}| \doteq 2^{nH(X)}$$

The honest fine print

$$2^{-n(H+\varepsilon)} \le p(x^n) \le 2^{-n(H-\varepsilon)}$$

Members are bounded near the typical scale, not exactly equiprobable.

The limits

Full explainer

Slide 5 of 6 · Q: What do the coding theorems deliver?

Remove redundancy. Then add it back on purpose.

Source coding · Kraft–McMillan bound, Huffman optimal

$$H(X) \le L^{*} < H(X) + 1 \qquad\text{with}\qquad \sum_i 2^{-\ell_i} \le 1$$

Channel coding · finite-alphabet memoryless channel

$$R < C \;\Longrightarrow\; \text{achievable, } P_e^{(n)} \to 0$$

These notes develop achievability; the converse is a TODO.

Edges & provenance

Full explainer

Slide 6 of 6 · Q: Where are the edges of these notes?

Beyond IID, and what this source is.

Memory · entropy rate

$$\bar H(X) = \lim_{n\to\infty} \tfrac{1}{n} H(X_1,\dots,X_n)$$

Continuous · what survives rescaling

$$h(aX) = h(X) + \log_2 |a|$$

Differential entropy shifts; mutual information is invariant to invertible coordinate change.

SourceSelective Fall 2022 notes for Michelle Effros's Caltech course. The PDF is unchanged; 20 corrections live in the errata.