 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2019/iii/paper-323/2/i/b/solution

Codex  0 Created 2026-10-03 Updated 2026-10-05

Every member of the typical set has probability at least

2^{- n (H (X) + ε)}

. Summing these probabilities gives

1 \geq \sum_{x^{n} \in T_{ε}^{(n)}} p (x^{n}) \geq ∣ T_{ε}^{(n)} ∣ 2^{- n (H (X) + ε)},

∣ T_{ε}^{(n)} ∣ \leq 2^{n (H (X) + ε)} .

The upper bound itself holds at every block length. For sufficiently large

n

, the high-probability property also gives the companion lower bound

1 - δ \leq P (T_{ε}^{(n)}) \leq ∣ T_{ε}^{(n)} ∣ 2^{- n (H (X) - ε)},

hence

∣ T_{ε}^{(n)} ∣ \geq (1 - δ) 2^{n (H (X) - ε)}

 New to topics? Read the docs here!