01 · The question · EngSci Abridged visual companion

Information has a budget.

Entropy prices uncertainty. Typicality turns that price into geometry. Coding theorems tell us which compression and communication schemes can exist.

How many bits must represent a source’s likely outputs—and how many bits can a noisy channel carry reliably?

Historical-source notice. The linked PDF is Aman's unchanged, selective Fall 2022 Ma126a condensation, offered without a correctness guarantee. It contains known formula errors, three TODO-only sections, and an empty Sardinas–Patterson heading. This companion states corrected results; read the page-located ledger.
02 · The operational spine

Two laws, two kinds of work.

The source branch measures what must be represented. The channel branch measures what can be transported. Mutual information connects observation to uncertainty, but source coding and channel coding remain distinct theorems.

Source: probability → description

Compression removes predictable redundancy.

Source-coding conceptual spine A probability law defines self-information. Its expectation is entropy. The AEP yields typical sequences, while lossless source coding makes entropy a description-length benchmark. probability law PX which outcomes are plausible? define ı(x) = −log₂ p(x) surprise of one outcome expectation H(X) = E[ı(X)] average uncertainty AEP source coding theorem typical count = 2nH+o(n) block rate → H bits/symbol
Distribution PXwhich outcomes are plausible?
↓ defines
ı(x) = −log₂ p(x)surprise of one outcome
↓ expectation
H(X) = E[ı(X)]average uncertainty
↓ IID AEP and source coding
typical count = 2nH+o(n)lossless block rate → H

For an IID finite-alphabet source, the typical-set and lossless block-coding statements are asymptotic.

Channel: observation → reliable rate

Channel coding adds structured redundancy.

Channel-coding conceptual spine An input distribution and channel law define a joint distribution. Their mutual information measures information carried. Maximizing over input distributions gives capacity. Rates below capacity are achievable for finite-alphabet discrete memoryless channels. input PX + channel PY|X what was sent, and how noise acts form joint; compare by KL I(X;Y) = D(PXY ‖ PXPY) information revealed by the output maximize over PX C = maxPₓ I(X;Y) capacity in bits per channel use direct coding theorem for R < C, error can tend to zero
Input PX + channel PY|Xform the joint law
↓ KL from independence
I(X;Y) = D(PXY ‖ PXPY)information carried
↓ maximize over PX
C = maxPₓ I(X;Y)capacity for the fixed channel
↓ direct coding theorem
R < C is achievableerror can tend to zero

The notes develop achievability. Their converse section—why rates above C fail—is a TODO.

03 · The accounting

Information is uncertainty you can account for.

For discrete variables with defined entropies, self-information adds before expectation does. That gives the chain rule and makes mutual information an exact accounting identity.

One outcome
ı(x) = −log₂ p(x)

p(x) > 0. Halving probability adds one bit.

Chain rule
H(X,Y) = H(X) + H(Y|X)

Add joint self-information, then take expectation.

Average uncertainty
H(X) = −Σ p(x) log₂ p(x)

Use the convention 0 log 0 = 0.

What Y reveals
I(X;Y) = H(X) − H(X|Y)

Also the KL divergence from the joint law to independent marginals.

Careful: “conditioning reduces entropy” is an average statement. A particular observation can make the conditional distribution more uncertain.

04 · The asymptotic bridge

Long IID sequences simplify at exponential scale.

For IID samples from a finite alphabet, −n−1 log₂ p(Xn) → H(X) in probability. Typical strings are not exactly equiprobable.

Typical-set geometry|Aε(n)| = 2nH+o(n)probability mass → 1
05 · The two limits

Remove redundancy. Then add it back on purpose.

In a common architecture, under suitable separation assumptions, source coding removes predictable redundancy before channel coding adds designed redundancy for reliable recovery despite noise.

Source coding

H(X) ≤ L* < H(X) + 1

Kraft and McMillan constrain lengths; Huffman attains the optimal symbol-prefix length. In the IID block limit, lossless rate approaches entropy.

Channel coding

R < C is achievable

For a finite-alphabet DMC, decoding error can tend to zero as block length grows. The converse is a TODO in these notes.

06 · Memory

Entropy rate

H̄ = limn→∞ H(X₁,…,Xₙ)/n

When the limit exists. For a stationary first-order Markov chain, it is the stationary average next-transition uncertainty.

06 · Continuity

Differential entropy

h(aX) = h(X) + log₂|a|, a ≠ 0

For an absolutely continuous variable with defined entropies. It changes with units; mutual information does not under invertible reparameterization.