Past exam of the mathematics course of the University of Cambridge 2015 iii Paper 66 4 ii c Solution 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.