 Competitive optimality of the Shannon code

ID: competitive-optimality-of-the-shannon-code

If the Shannon length is

l_{S} (x) = ⌈ lo g_{2} (1/ p_{x})⌉

and

l_{C}

is the length of any binary decipherable code, then

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

Thus the probability that the Shannon code loses to another code by

k

or more bits decreases exponentially in

k

 New to topics? Read the docs here!