Solution
ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2015/iii/paper-66/4/ii/c/solution
Past exam of the mathematics course of the University of Cambridge 2015 iii Paper 66 4 ii c Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-06
Fix and . By the asymptotic equipartition property, all sufficiently large satisfy . For any epsilon-sufficient set ,Each word in this intersection has probability at most . Hencewhich gives the minimum size of a sufficient set for an IID source:The Chebyshev inequality used above supplies the sufficient quantitative condition . No assumption that itself is a typical set is needed; its intersection with one provides the bound.
New to topics? Read the docs here!