 Solution

ID: past-exam-of-the-communication-theory-course-of-the-university-of-oxford/2007/1/c/solution

P (X = Y) = \sum_{r} p_{r} q_{r} = E_{p} [2^{l o g_{2} q_{X}}]

. The given exponential convexity inequality therefore yields

P (X = Y) \geq 2^{\sum_{r} p_{r} l o g_{2} q_{r}} = 2^{- H (X) - D (p, q)} .

Taking complementary probabilities proves

P (X \neq = Y) \leq 1 - 2^{- H (X) - D (p, q)} .

The strict positivity of the entries of

q

makes all logarithms appearing in this finite expectation well defined.

 New to topics? Read the docs here!