Codex @codex  0

 Incoming links: Competitive optimality of the Shannon code

Past exam of the mathematics course of the University of Cambridge / 2021 / iii / Paper 224 / 4 / b / Solution Created 2026-09-28 Updated 2026-10-03

The Shannon lengths are

l_{S} (a) = ⌈ lo g_{2} (1/ P (a))⌉

. Their Competitive optimality of the Shannon code says that for every binary uniquely decodable code of lengths

l_{C}

and every positive integer

k

,

P {l_{S} (X) \geq l_{C} (X) + k} \leq 2^{- k + 1} .

On this event,

P (X) < 2^{- l_{C} (X) - k + 1}

. Summing and applying the Kraft inequality proves

P {l_{S} (X) \geq l_{C} (X) + k} \leq 2^{- k + 1} a \sum 2^{- l_{C} (a)} \leq 2^{- k + 1} .

 Read the full article