Engineering & Science, Abridged · Ma126a · narrated cut

Full explainer · Ma126a information theory

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.

H

Source branch. A source distribution defines surprise. Its average is entropy. Typicality and coding turn entropy into a description-length limit.

compression

C

Channel branch. An input distribution and a channel law define mutual information. Maximizing over the input gives capacity.

communication

Careful The 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.

−log₂ p

Self-information. Halving the probability adds exactly one bit.

surprise

H(X,Y)

Chain rule. Joint entropy is H(X) plus H(Y given X). Joint self-information adds; expectation keeps the sum.

= H(X) + H(Y|X)

I(X;Y)

Mutual information, two ways. Average uncertainty removed by Y, and the Kullback–Leibler divergence from the joint law to independent marginals.

two readings, one number

The bridge

Full explainer

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

The A-E-P turns averages into counts.

For IID finite-alphabet samples, self-information per symbol converges in probability to entropy.

2ⁿᴺ

The typical set. Nearly all probability mass sits in about 2 to the nH sequences, at exponential scale.

members bounded near scale

≠

Not equiprobable. Members are bounded near that scale, not exactly equal.

the honest fine print

The limits

Full explainer

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

Remove redundancy. Then add it back on purpose.

Kraft

Lossless codes are constrained. Kraft and McMillan bound code lengths; Huffman minimizes expected symbol-prefix length.

source side

R < C

Below capacity, error can vanish. For a finite-alphabet memoryless channel, rates below capacity are achievable with error tending to zero.

channel side

Scope The 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.

Hₖ

Memory. Entropy rate replaces one-symbol entropy when its limit exists.

processes

h(X)

Continuous variables. Rescaling changes differential entropy; mutual information survives invertible coordinate changes.

what survives

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