The Lumenary · Advanced undergraduate

Information theory

Name: ______________________

Date: ______________________

You will learn to

Compute entropy, joint and conditional entropy, relative entropy and mutual information, and prove their basic inequalities from Gibbs' inequality
Prove Kraft's inequality, construct Huffman codes and prove that the optimal expected length $L^*$ of a prefix code satisfies $H \le L^* < H + 1$
Explain the asymptotic equipartition property and state Shannon's source coding theorem
Compute the capacity of the binary symmetric and erasure channels, and state the noisy-channel coding theorem and its converse
Distinguish Shannon information from meaning, and prove that no compressor can shorten every file

1.
A source emits one of $8$ symbols, all equally likely. What is its entropy, in bits?
2.
A binary prefix code already contains the codewords $0$ and $10$ . What is the largest number of further codewords of length exactly $3$ that can be added while keeping the code prefix-free?
3.
Which statements about the mutual information $I(X; Y)$ of finite random variables are true? (Choose all that apply.)
- A. $I(X; Y) = I(Y; X)$ .
- B. $I(X; Y) \ge 0$ , with equality if and only if $X$ and $Y$ are independent.
- C. $I(X; Y) \le \min(H(X), H(Y))$ .
- D.Applying a function $g$ to $Y$ can increase the information it carries: $I(X; g(Y))$ may exceed $I(X; Y)$ .
4.
In the proof of Gibbs' inequality we bound $\sum_x p(x)\ln\frac{q(x)}{p(x)} \le \sum_x \big(q(x) - p(x)\big)$ . Which fact justifies this step?
- A. $\ln t \le t - 1$ for all $t > 0$ , applied with $t = q(x)/p(x)$ and multiplied by $p(x) \ge 0$ .
- B. $\ln$ is increasing.
- C. $\sum_x q(x) \le 1$ .
- D. $\ln t \ge 0$ for $t \ge 1$ .
5.
Build a Huffman code for four symbols with probabilities $0.4, 0.3, 0.2, 0.1$ . What is the expected codeword length, in tenths of a bit (so $1.5$ bits would be $15$ )?
6.
A binary symmetric channel flips each bit independently with probability $p$ . For which values of $p$ is its capacity exactly $1$ bit per use? (Choose all that apply.)
- A. $p = 0$
- B. $p = 1$
- C. $p = \tfrac12$
- D. $p = 0.01$
7.
A start-up claims its lossless compressor shortens every file of exactly $1000$ bits by at least one bit. What is wrong?
- A.There are $2^{1000}$ such files but only $2^{1000} - 1$ files shorter than $1000$ bits, so two files would get the same output and could not both be recovered.
- B.Nothing in principle: with a good enough model, every file can be compressed below its entropy.
- C.It is possible, but the compressor would be too slow.
- D.Only files with meaningful content can be compressed, and random files have no meaning.
8.
Which Lean statement formalises Kraft's inequality for prefix codes? (u <+: v means u is a prefix of v.)
- A.(hpf : ∀ u ∈ C, ∀ v ∈ C, u <+: v → u = v) : ∑ w ∈ C, (1 / 2 : ℝ) ^ w.length ≤ 1
- B.(hpf : ∀ u ∈ C, ∀ v ∈ C, u <+: v → u = v) : ∑ w ∈ C, (1 / 2 : ℝ) ^ w.length = 1
- C.(hpf : ∀ u ∈ C, ∀ v ∈ C, u ≠ v) : ∑ w ∈ C, (1 / 2 : ℝ) ^ w.length ≤ 1
- D.(hpf : ∀ u ∈ C, ∀ v ∈ C, u <+: v → u = v) : ∑ w ∈ C, (2 : ℝ) ^ w.length ≤ 1
9.
Write entropy(probs) returning $-\sum p\log_2 p$ in bits (skipping zero probabilities), and kl(p, q) returning $D(p\,\|\,q) = \sum p\log_2(p/q)$ (also skipping terms with $p = 0$ ). The tests check examples from the lesson, Gibbs' inequality on random distributions, and the asymmetry of relative entropy.
Computational — Practice

Answer key — Information theory

1.
$H = -\sum_{i=1}^8 \tfrac18\log_2\tfrac18 = \log_2 8 = 3$ bits — exactly the number of yes/no questions needed to identify the symbol, and the length of a fixed-length binary code. By Gibbs' inequality no distribution on $8$ symbols has larger entropy.
2.
The existing codewords use $2^{-1} + 2^{-2} = \tfrac34$ of the Kraft budget, leaving $\tfrac14 = 2 \cdot 2^{-3}$ : at most $2$ codewords of length $3$ . They exist: $110$ and $111$ , giving the complete code $\{0, 10, 110, 111\}$ with Kraft sum exactly $1$ .
3.
The first three are true: symmetry from $I = H(X) + H(Y) - H(X, Y)$ ; non-negativity and the independence criterion from $I = D(p_{XY}\|p_Xp_Y)$ and Gibbs; the bound from $H(X \mid Y) \ge 0$ . Processing cannot create information about $X$ : $I(X; g(Y)) \le I(X; Y)$ .
4.
For $p(x) > 0$ : $p(x)\ln\frac{q(x)}{p(x)} \le p(x)\big(\frac{q(x)}{p(x)} - 1\big) = q(x) - p(x)$ by $\ln t \le t - 1$ ; for $p(x) = 0$ the term is $0 \le q(x)$ . The hypothesis $\sum q \le 1$ then makes the total $\le 0$ , and equality in $\ln t \le t - 1$ only at $t = 1$ gives the equality case.
5.
Merges: $0.1 + 0.2 = 0.3$ ; $0.3 + 0.3 = 0.6$ ; $0.4 + 0.6 = 1$ . The lengths are $1, 2, 3, 3$ , so $L = 0.4 + 0.6 + 0.6 + 0.3 = 1.9$ bits, i.e. $19$ tenths. The entropy is $H \approx 1.846$ bits, so $H \le L < H + 1$ as the theorem says.
6.
$C = 1 - H_2(p) = 1$ exactly when $H_2(p) = 0$ , i.e. $p = 0$ or $p = 1$ . Capacity measures how much the output reveals about the input; a deterministic flip reveals everything. It is $0$ at $p = \tfrac12$ and about $0.919$ at $p = 0.01$ .
7.
A lossless compressor must be injective. There are $2^{1000}$ inputs but only $\sum_{k<1000}2^k = 2^{1000} - 1$ possible shorter outputs, so by the pigeonhole principle two inputs collide. This is the theorem no_universal_compression in the lesson's Lean module.
8.
Statement (a). (b) claims equality, which fails for incomplete codes; (c) has an impossible hypothesis and is therefore vacuously true — a classic formalisation trap; (d) uses the wrong weights.
9.
```
import math

def entropy(probs):
    return -sum(p * math.log2(p) for p in probs if p > 0)

def kl(p, q):
    return sum(a * math.log2(a / b) for a, b in zip(p, q) if a > 0)
```
The random tests check Gibbs' inequality $D(p\|q) \ge 0$ and its corollary $H(p) \le \log_2 5$ on $200$ examples — evidence, not proof; the proof is in the lesson (and in Lean).