Entropy & Shannon's Source Coding Theorem

Claude Shannon, at Bell Labs, published a two-part paper in the Bell System Technical Journal (July and October 1948).

It asked one clean question: what is the least number of bits needed to send a message, with or without noise?

His answer split into two theorems:

• Source coding (this deck): data can be squeezed down to its entropy H, and no further.
• Channel coding (next deck): a noisy channel has a capacity C, and you can send below it with tiny error.

Key idea: information is about uncertainty, not meaning. The content of a message does not matter, only how likely it was.

Why a log? We want three things:

• Certain events say nothing: I(1) = 0.
• Rare events say more: I goes down as p goes up.
• Independent events add: I(pq) = I(p) + I(q).

The only continuous functions that turn products into sums are logs. So I(p) = −K log p. Base 2 picks the unit: the bit.

Base e gives nats. 1 nat = 1/ln 2 ≈ 1.4427 bits.

import math

def surprise(p):
    return 0.0 - math.log2(p)

for p in [1, 0.5, 0.25, 1/6, 0.01]:
    print(f"p={p:<6.4g} surprise={surprise(p):.3f} bits")

p=1      surprise=0.000 bits
p=0.5    surprise=1.000 bits
p=0.25   surprise=2.000 bits
p=0.1667 surprise=2.585 bits
p=0.01   surprise=6.644 bits

A fair coin flip is 1 bit. Two flips are 2 bits. A 1-in-100 event is about 6.6 bits: like guessing 6 or 7 yes/no questions right.

0.0 - x avoids printing -0.000 when p = 1.

Three ways to read H(X):

• The expected surprise of one draw.
• The uncertainty before you look.
• The fewest bits per symbol any lossless code can use on average (the theorem we will prove).

H depends only on the probabilities, not on the labels. Renaming outcomes does not change it.

def H(probs):
    """Shannon entropy in bits. Terms with p=0 contribute 0."""
    return 0.0 - sum(p * math.log2(p) for p in probs if p > 0)

print(f"{H([0.5, 0.5]):.4f}")        # fair coin
print(f"{H([0.9, 0.1]):.4f}")        # biased coin
print(f"{H([1/6] * 6):.4f}")         # fair die
print(f"{H([1.0]):.4f}")             # certain

1.0000
0.4690
2.5850
0.0000

A weather station sends one of four reports. Find the entropy with pencil and paper.

1. Step 1. Surprise of each outcome: log₂(1/p).
2. Step 2. Weight each surprise by how often it happens.
3. Step 3. Add. That average is H.

Shannon asked: what properties should a measure of uncertainty H(p₁,…,p_n) have?

1. Continuity: H is continuous in the p_i.
2. Monotone: for uniform choices, A(n) = H(1/n,…,1/n) grows with n.
3. Grouping: if a choice is split into two steps, H is the first step's H plus the weighted H of the second step.

Proof sketch. Grouping on uniform choices gives A(s^m) = m·A(s). With monotonicity this forces A(n) = K log n. For rational p_i = n_i/N, split a uniform choice of N into groups of size n_i: K log N = H(p) + ∑ p_i K log n_i. Solve for H(p). Continuity extends to all real p. ∎

p = [0.5, 0.25, 0.25]
lhs = H(p)
rhs = H([0.5, 0.5]) + 0.5 * H([0.5, 0.5])
print(f"{lhs:.4f} {rhs:.4f}")

1.5000 1.5000

Other axiom sets (Khinchin 1957, Faddeev 1956) give the same answer. Entropy is not a guess; it is forced.

The curve above is drawn from 101 real points of h2(p), computed in the test file.

• Symmetric: h(p) = h(1−p).
• Concave, with h''(p) = −1/(p(1−p) ln 2) < 0.
• Steep at the ends: h'(p) = log₂((1−p)/p) → ∞ as p → 0.

def h2(p):
    return H([p, 1 - p])

for p in [0.0, 0.1, 0.11, 0.25, 0.5]:
    print(f"h({p}) = {h2(p):.4f}")

h(0.0) = 0.0000
h(0.1) = 0.4690
h(0.11) = 0.4999
h(0.25) = 0.8113
h(0.5) = 1.0000

Lower bound. Each 0 ≤ p ≤ 1, so log(1/p) ≥ 0. Every term p log(1/p) is ≥ 0. The sum is 0 only if every term is 0, so each p is 0 or 1.

Upper bound. Let Z = 1/p(X). Since log is concave:

H(X) = E[ log 1/p(X) ]
    ≤ log E[ 1/p(X) ]
    = log ∑_x p(x) · 1/p(x)
    = log n.  ∎

Equality needs 1/p(x) constant, so p(x) = 1/n for all x.

Reading: uniform is the most uncertain. A fixed-length code with ⌈log₂ n⌉ bits is optimal only when the source is (close to) uniform. Any skew is room to compress.

Same proof in other words: log n − H(X) = D(p ‖ u) ≥ 0, the KL divergence from uniform.

Proof. log p(x,y) = log p(x) + log p(y|x). Take −E[·] of both sides. ∎

Conditioning reduces entropy: H(Y|X) ≤ H(Y), with equality iff independent. (On average! A single H(Y|X=x) can be bigger.)

# joint distribution of (Weather, Umbrella)
P = {("sun", "no"): 0.45, ("sun", "yes"): 0.05,
     ("rain", "no"): 0.10, ("rain", "yes"): 0.40}
def marginal(P, i):
    m = Counter()
    for k, v in P.items():
        m[k[i]] += v
    return m
HXY = H(P.values())
HX = H(marginal(P, 0).values())
HY = H(marginal(P, 1).values())
HY_given_X = HXY - HX            # chain rule
I = HX + HY - HXY
print(f"H(X,Y)={HXY:.4f} H(X)={HX:.4f} H(Y)={HY:.4f}")
print(f"H(Y|X)={HY_given_X:.4f} I(X;Y)={I:.4f}")

H(X,Y)=1.5955 H(X)=1.0000 H(Y)=0.9928
H(Y|X)=0.5955 I(X;Y)=0.3973

The test file also computes H(Y|X) directly from the definition and checks it equals HXY - HX.

• How much knowing Y cuts your doubt about X.
• Symmetric: I(X;Y) = I(Y;X).
• I(X;Y) = D(p(x,y) ‖ p(x)p(y)) ≥ 0, and 0 iff independent.
• I(X;X) = H(X): entropy is self-information.

In the weather example: seeing the umbrella tells you 0.397 bits of the 1 bit of weather doubt.

Mutual information is the star of the next deck: channel capacity is max I(X;Y).

The Venn picture is exact for two variables. With three or more, the middle region I(X;Y;Z) can be negative, so treat the picture with care.

Model English as letters a–z plus space: 27 symbols. A uniform guess would need log₂ 27 ≈ 4.755 bits per character.

Real letters are not uniform. Below, TEXT holds the opening paragraph of Dickens' A Tale of Two Cities (in the test file).

letters = [c for c in TEXT.lower() if c.isalpha() or c == " "]
text27 = "".join(letters)
counts = Counter(text27)
n = len(text27)
H1 = H(c / n for c in counts.values())
print(f"chars={n} symbols={len(counts)}")
print(f"H1 = {H1:.3f} bits/char   (log2 27 = {math.log2(27):.3f})")
print("top:", " ".join(f"{'_' if c == ' ' else c}:{k/n:.3f}"
                       for c, k in counts.most_common(6)))

chars=907 symbols=25
H1 = 3.962 bits/char   (log2 27 = 4.755)
top: _:0.191 e:0.121 t:0.080 i:0.065 o:0.064 a:0.063

Using context lowers it more. The entropy of the next letter given the last one:

big = Counter(zip(text27, text27[1:]))
nb = sum(big.values())
H2joint = H(v / nb for v in big.values())
first = Counter(a for a, _ in zip(text27, text27[1:]))
Hfirst = H(v / nb for v in first.values())
print(f"H(X2|X1) = {H2joint - Hfirst:.3f} bits/char")

H(X2|X1) = 2.814 bits/char

This paragraph lacks z and x, so only 25 symbols appear. Small samples also make the bigram number too low (see Pitfalls).

Each extra letter of context can only lower H(X_n | past), because conditioning reduces entropy. The chain rule then says the long-run bits per letter is this limit.

Modern language models are entropy estimators. A model's cross-entropy loss in bits per character is an upper bound on the true entropy rate.

• Nonsingular: C is one-to-one.
• Uniquely decodable (UD): C* is one-to-one. Every bit string splits in at most one way.
• Prefix (instantaneous): no codeword is a prefix of another. You can decode each symbol the moment its last bit arrives.

prefix ⊂ UD ⊂ nonsingular ⊂ all codes

The average length is L(C) = ∑_x p(x) · ℓ(x). Our goal: make L small while staying UD.

Column 2: 010 could be "2", "1 4" or "3 1". Column 3 is UD, but after reading 11 you must look ahead to see if a 0 follows. Column 4 decodes at once.

Prefix-freeness is easy to check. UD is harder: a code can fail only for long strings. The Sardinas–Patterson test (1953) decides it in finite time.

1. Let S₁ be the "dangling suffixes": w such that a w = b for codewords a ≠ b.
2. Build S_i+1 from suffixes between S_i and C, in both directions.
3. If some S_i contains a codeword: not UD.
4. If the sets start repeating or go empty: UD.

Only finitely many suffixes exist, so the loop must stop.

Why it works: a dangling suffix that is itself a codeword marks the point where two different parsings of the same bits line up again.

def uniquely_decodable(C):
    """Sardinas-Patterson test."""
    C = set(C)
    def dangling(A, B):
        return {b[len(a):] for a in A for b in B if b != a and b.startswith(a)}
    S = dangling(C, C)
    seen = set()
    while S:
        if S & C:
            return False
        key = frozenset(S)
        if key in seen:
            return True
        seen.add(key)
        S = dangling(S, C) | dangling(C, S)
    return True
print(uniquely_decodable(["0", "10", "110", "111"]))   # prefix
print(uniquely_decodable(["0", "01", "011", "0111"]))  # UD, not prefix
print(uniquely_decodable(["0", "01", "10"]))           # "010" is ambiguous

True
True
False

So UD codes buy you nothing over prefix codes: any lengths a UD code can reach, a prefix code can reach too. From here on we only need prefix codes.

Think of 2^−ℓ as a budget. Short codewords are costly. The total budget is 1.

def kraft(lengths, D=2):
    return sum(D ** -l for l in lengths)
print(kraft([1, 2, 3, 3]))      # complete prefix code
print(kraft([1, 2, 2, 3]))      # impossible
print(kraft([2, 2, 3]))         # room to spare

1.0
1.125
0.625

A prefix code is the set of leaves of a D-ary tree. A codeword ends its branch, so no other codeword can live under it.

Prefix codes: count leaves

Let ℓ_max be the longest length. In the full tree of depth ℓ_max there are D^ℓ_max leaves.

A codeword at depth ℓ_i owns the D^{ℓ_max−ℓ_i} leaves under it. Prefix-free means these sets do not overlap. So

∑_i D^{ℓ_max−ℓ_i} ≤ D^ℓ_max  ⇒  ∑_i D^−ℓ_i ≤ 1.

Converse: build it

Sort lengths ℓ₁ ≤ ℓ₂ ≤ …. Take the first free node at depth ℓ₁, then at ℓ₂, and so on. Each choice uses up a D^−ℓ share of the leaves. Since the total is at most 1, a free node is always left. (Code on the next slide.)

UD codes: McMillan's trick

Let S = ∑_x D^−ℓ(x). Raise it to the power k:

S^k = ∑_x1…xk D^{−(ℓ(x₁)+…+ℓ(x_k))} = ∑_m=1^kℓ_max A_m D^−m

Here A_m counts the k-symbol strings whose code has m bits. UD means those codes are all different strings of length m. So A_m ≤ D^m, and

S^k ≤ ∑_m=1^kℓ_max 1 = k ℓ_max.

If S > 1, then S^k grows exponentially but kℓ_max only linearly. That fails for large k. So S ≤ 1. ∎

Neat move: UD is a claim about all strings, so look at long strings and let k → ∞.

def code_from_lengths(lengths):
    """Canonical prefix code: assign codewords in order of length."""
    assert kraft(lengths) <= 1
    code, words, prev = 0, [], None
    for l in sorted(lengths):
        if prev is not None:
            code = (code + 1) << (l - prev)
        words.append(format(code, f"0{l}b"))
        prev = l
    return words
print(code_from_lengths([1, 2, 3, 3]))
print(code_from_lengths([2, 2, 3, 3, 3]))

def is_prefix_free(words):
    return not any(a != b and b.startswith(a) for a in words for b in words)

['0', '10', '110', '111']
['00', '01', '100', '101', '110']

This is the canonical code used by DEFLATE (ZIP, gzip, PNG). The step (code + 1) << (l - prev) moves to the next free node, then walks down to the new depth.

• The encoder only has to send the lengths, not the codewords. The decoder rebuilds the same code.
• In the second example Kraft sum is 2·¼ + 3·⅛ = ⅞ < 1, so one leaf (111) is left unused.
• Unused leaves mean wasted budget. An optimal code has Kraft sum exactly 1 (a complete tree).

The test file checks is_prefix_free on both outputs.

Equality L = H holds iff every p(x) is a power of 2 (a dyadic source) and ℓ(x) = −log₂ p(x).

Proof of L ≥ H

Let c = ∑_i 2^−ℓ_i. By McMillan, c ≤ 1. Define r_i = 2^−ℓ_i/c, a distribution.

L − H = ∑ p_iℓ_i + ∑ p_i log p_i
    = ∑ p_i log( p_i / 2^−ℓ_i )
    = ∑ p_i log( p_i / r_i ) − log c
    = D(p ‖ r) + log(1/c)  ≥ 0 + 0.  ∎

The code's lengths define a distribution r. The extra bits you pay are exactly the KL divergence between the true p and the one your code "believes", plus the waste from an incomplete tree.

Shannon code: ℓ_i = ⌈log₂(1/p_i)⌉

Kraft holds: ℓ_i ≥ log(1/p_i), so 2^−ℓ_i ≤ p_i. Summing, ∑ 2^−ℓ_i ≤ ∑ p_i = 1. So a prefix code with these lengths exists.

Short enough: ℓ_i < log(1/p_i) + 1. Multiply by p_i and sum:

L = ∑ p_iℓ_i < ∑ p_i log(1/p_i) + 1 = H + 1.  ∎

Rounding up each length costs less than 1 bit per symbol. That +1 is the price of using a whole number of bits.

def shannon_lengths(p):
    return [math.ceil(-math.log2(x)) for x in p]
p = [0.4, 0.3, 0.2, 0.1]
l = shannon_lengths(p)
L = sum(pi * li for pi, li in zip(p, l))
print(l, f"L={L:.3f} H={H(p):.3f} kraft={kraft(l):.4f}")

[2, 2, 3, 4] L=2.400 H=1.846 kraft=0.6875

The bound holds: 1.846 ≤ 2.400 < 2.846. But the Kraft sum is only 0.6875. Almost a third of the budget is wasted.

Shannon codes are within 1 bit of H but not optimal. Huffman will get L = 1.9 on this same source.

The Shannon code is still the heart of the proof. It is also exactly what arithmetic coding does, but for a whole message at once, so the +1 is paid once, not per symbol.

The +1 hurts when H is small. Fix: code blocks of k symbols as one super-symbol.

For a stationary (not i.i.d.) source the same argument gives L_k/k → ℋ, the entropy rate.

Cost: the alphabet grows as |𝒳|^k. At k=8 a binary source already needs a 256-leaf tree. This is why arithmetic coding wins in practice.

def block_rate(p1, k):
    probs = {}
    for bits_ in itertools.product("01", repeat=k):
        pr = 1
        for b in bits_:
            pr *= p1 if b == "1" else 1 - p1
        probs["".join(bits_)] = pr
    c = huffman(probs)
    return sum(probs[s] * len(c[s]) for s in probs) / k
p1 = 0.1
print(f"H = {h2(p1):.4f} bits/symbol")
for k in [1, 2, 3, 4, 6, 8]:
    print(f"k={k}: {block_rate(p1, k):.4f} bits/symbol")

H = 0.4690 bits/symbol
k=1: 1.0000 bits/symbol
k=2: 0.6450 bits/symbol
k=3: 0.5327 bits/symbol
k=4: 0.4926 bits/symbol
k=6: 0.4702 bits/symbol
k=8: 0.4758 bits/symbol

Note k=8 is slightly worse than k=6. The bound H + 1/k is a guarantee, not a promise of steady progress.

Proof. By independence, −(1/n) log p(Xⁿ) = (1/n) ∑_i (−log p(X_i)). This is an average of i.i.d. terms with mean E[−log p(X)] = H. The weak law of large numbers finishes it. ∎

In words: almost every long sequence you will actually see has probability about 2^−nH. All "likely" sequences are about equally likely. That is the "equipartition".

It is the information-theory version of the law of large numbers. A random 1000-flip sequence of a 20% coin has about 200 ones, so its probability is about 0.2²⁰⁰0.8⁸⁰⁰ = 2^{−1000·h(0.2)}.

random.seed(7)
p1 = 0.2
Hs = h2(p1)
for n_ in [10, 100, 1000, 10000]:
    x = [1 if random.random() < p1 else 0 for _ in range(n_)]
    k = sum(x)
    logp = k * math.log2(p1) + (n_ - k) * math.log2(1 - p1)
    print(f"n={n_:>5}: -1/n log2 p(x) = {-logp / n_:.4f}   (H = {Hs:.4f})")

n=   10: -1/n log2 p(x) = 1.1219   (H = 0.7219)
n=  100: -1/n log2 p(x) = 0.7619   (H = 0.7219)
n= 1000: -1/n log2 p(x) = 0.7539   (H = 0.7219)
n=10000: -1/n log2 p(x) = 0.7175   (H = 0.7219)

A second proof of the source coding theorem

Index the typical set with n(H+ε)+1 bits, flag bit 0. Send anything else raw with flag 1. The average is n(H + ε') bits. So H bits per symbol suffice.

def typical_stats(n_, p1, eps):
    Hs = h2(p1)
    prob = 0.0
    count = 0
    for k in range(n_ + 1):
        rate = -(k * math.log2(p1) + (n_ - k) * math.log2(1 - p1)) / n_
        if abs(rate - Hs) <= eps:
            count += math.comb(n_, k)
            logterm = (math.lgamma(n_ + 1) - math.lgamma(k + 1) - math.lgamma(n_ - k + 1)
                       + k * math.log(p1) + (n_ - k) * math.log(1 - p1))
            prob += math.exp(logterm)
    return prob, math.log2(count) / n_
for n_ in [100, 500, 1000, 2000]:
    prob, lg = typical_stats(n_, 0.2, 0.05)
    print(f"n={n_:>4}: P(typical)={prob:.3f}  log2|A|/n={lg:.3f}  (H={h2(0.2):.3f}, all=1.000)")

n= 100: P(typical)=0.468  log2|A|/n=0.731  (H=0.722, all=1.000)
n= 500: P(typical)=0.838  log2|A|/n=0.759  (H=0.722, all=1.000)
n=1000: P(typical)=0.952  log2|A|/n=0.765  (H=0.722, all=1.000)
n=2000: P(typical)=0.995  log2|A|/n=0.767  (H=0.722, all=1.000)

With ε = 0.05: the typical set soon holds 99.5% of the probability. Yet it has only 2^0.767n of the 2ⁿ sequences: at n=2000 that is a fraction 2⁻⁴⁶⁶.

The single most likely sequence (all zeros) is not typical. Typical is not the same as most probable.

Fano's method (1949): sort symbols by probability. Split the list into two parts with totals as equal as possible. Give the left part 0 and the right part 1. Recurse.

def fano(items):
    """items: list of (symbol, p) sorted by p desc -> {symbol: code}"""
    if len(items) == 1:
        return {items[0][0]: ""}
    total, run, best, cut = sum(p for _, p in items), 0, None, 1
    for i in range(1, len(items)):
        run += items[i - 1][1]
        diff = abs(total - 2 * run)
        if best is None or diff < best:
            best, cut = diff, i
    left = {s: "0" + c for s, c in fano(items[:cut]).items()}
    right = {s: "1" + c for s, c in fano(items[cut:]).items()}
    return {**left, **right}

q = [("a", .35), ("b", .17), ("c", .17), ("d", .16), ("e", .15)]
fc, hc = fano(q), huffman(dict(q))
Lf = sum(p * len(fc[s]) for s, p in q)
Lh = sum(p * len(hc[s]) for s, p in q)
print(f"Fano L={Lf:.2f}  Huffman L={Lh:.2f}  H={H(p for _, p in q):.3f}")

Fano L=2.31  Huffman L=2.30  H=2.233

• Top-down splitting is greedy. A bad early split can never be undone.
• Fano's code is always within 2 bits of H, but it is not always optimal.
• Here it loses to Huffman by 0.01 bits per symbol: small, but real.

Fano set this as a class problem at MIT: find the best code. His student David Huffman found it by building the tree bottom up instead.

def huffman(freqs):
    """freqs: {symbol: weight} -> {symbol: codeword}"""
    if len(freqs) == 1:
        return {s: "0" for s in freqs}
    tie = itertools.count()               # break ties without comparing dicts
    heap = [(w, next(tie), {s: ""}) for s, w in freqs.items()]
    heapq.heapify(heap)
    while len(heap) > 1:
        w1, _, a = heapq.heappop(heap)    # two lightest subtrees
        w2, _, b = heapq.heappop(heap)
        merged = {s: "0" + c for s, c in a.items()}
        merged.update({s: "1" + c for s, c in b.items()})
        heapq.heappush(heap, (w1 + w2, next(tie), merged))
    return heap[0][2]

p = {"a": 0.4, "b": 0.3, "c": 0.2, "d": 0.1}
code = huffman(p)
L = sum(p[s] * len(c) for s, c in code.items())
print(dict(sorted(code.items())), f"L={L:.2f} H={H(p.values()):.3f}")

{'a': '0', 'b': '10', 'c': '111', 'd': '110'} L=1.90 H=1.846

1. Put each symbol in a min-heap by weight.
2. Pop the two lightest trees. Join them under a new node whose weight is their sum.
3. Repeat until one tree is left.

L = 1.9 vs Shannon's 2.4 and H = 1.846. Runs in O(n log n).

Order p₁ ≥ p₂ ≥ … ≥ p_m. Some optimal code has:

1. Longer for rarer: p_i > p_j ⇒ ℓ_i ≤ ℓ_j. Else swap the two codewords: L changes by (p_i−p_j)(ℓ_j−ℓ_i) < 0, a contradiction.
2. Full tree: every inner node has 2 children. Else move the lone child up and save a bit.
3. Siblings at the bottom: the two rarest symbols, m and m−1, are siblings at max depth. (By 1 and 2, the deepest level has a sibling pair; swap the rarest two into it.)

Induction on m

Merge the two rarest symbols into one symbol of weight p_m−1+p_m. Call the new code problem P'. Any tree T of the form in step 3 comes from a tree T' for P' by splitting one leaf, and

L(T) = L(T') + p_m−1 + p_m.

The extra term is a constant. So minimizing L(T) is the same as minimizing L(T'). That is exactly Huffman's step: merge, then solve the smaller problem. The base case m = 2 is trivial. ∎

Greedy is safe here because of the exchange argument (step 3) plus optimal substructure (the merge identity). Fano's top-down split has no such guarantee.

Huffman is optimal among codes that give each symbol a whole number of bits. It is not optimal among all compressors.

code = huffman(counts)
bits = sum(len(code[c]) for c in text27)
print(f"Huffman: {bits / n:.3f} bits/char   H1: {H1:.3f}   "
      f"fixed: {math.ceil(math.log2(len(counts)))}   ASCII: 8")

# round trip decode
enc = "".join(code[c] for c in text27)
rev = {v: k for k, v in code.items()}
out, buf = [], ""
for b in enc:
    buf += b
    if buf in rev:
        out.append(rev[buf]); buf = ""
assert "".join(out) == text27

Huffman: 3.998 bits/char   H1: 3.962   fixed: 5   ASCII: 8

Decoding needs no separators: prefix-freeness means the first match in rev is the right one.

Huffman is only 0.036 bits above H₁. When no symbol is very likely, the +1 worst case is far away.

To beat H₁ you must use context: model p(x_n | past). The source coding theorem then applies to the conditional distribution. This is how PPM, LZ77 and neural compressors win.

Every codeword is at least 1 bit. For a very skewed source that is a disaster:

p = {"x": 0.99, "y": 0.01}
c = huffman(p)
L = sum(p[s] * len(c[s]) for s in p)
print(f"H={H(p.values()):.4f}  Huffman L={L:.4f}  waste={L / H(p.values()):.1f}x")
for k in [1, 4, 8]:
    print(f"blocks of {k}: {block_rate(0.01, k):.4f} bits/symbol")

H=0.0808  Huffman L=1.0000  waste=12.4x
blocks of 1: 1.0000 bits/symbol
blocks of 4: 0.2727 bits/symbol
blocks of 8: 0.1572 bits/symbol

Blocks help, but even 256-symbol blocks are still 2× off. Adaptive models make it worse: the tree must be rebuilt when p changes.

• Total cost < nH + 2 bits: the overhead is paid once per message, not per symbol.
• Models can change every symbol (adaptive, context-mixing, neural).
• Modern cousin: ANS (asymmetric numeral systems, Jarek Duda), as fast as Huffman, used in zstd, Apple LZFSE and JPEG XL.

1. What is the entropy of a fair 8-sided die?
2. A fair coin has 1 bit of entropy. How many nats is that?
3. Can a prefix code have codeword lengths 1, 2, 2, 3?
4. Huffman gives lengths 1, 2, 3, 3 for p = (0.4, 0.3, 0.2, 0.1). Is the average length above, below or equal to H?
5. X and Y are independent fair coins. What is I(X;Y)? What is H(X,Y)?
6. Why can no lossless compressor shrink every 1000-bit file?

Try each one before you look to the right.

Entropy is the price of information: the fewest bits per symbol that any lossless code can pay.

• You cannot beat H on average (Gibbs + Kraft).
• You can get within 1 bit per symbol (Shannon code), and within 1/k with blocks.
• Huffman is the best whole-bit code; arithmetic coding and ANS close the last gap.
• On real English: letters give 3.96 bits, context brings it near 1 bit.

Next: what if the channel is noisy? Shannon's second theorem says there is a speed limit, the capacity C, and below it errors can be made as rare as you like.