 Solution

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

Use the convention

0 lo g_{2} 0 = 0

. On the positive support of

p

D (p, q) = - \sum_{p_{r} > 0} p_{r} lo g_{2} (q_{r} / p_{r}) \geq c \sum_{p_{r} > 0} (p_{r} - q_{r}) \geq 0.

The logarithm is strictly concave, so its supporting line at one has equality only there. More explicitly, the given global bound forces

c = 1/ lo g_{e} 2

by differentiation at one, and

x - 1 - lo g_{e} x

vanishes only at one. Equality above therefore requires

p_{r} = q_{r}

on the positive support, and no mass of

q

outside it. Thus equality holds exactly when $p = q$ .

For the uniform distribution

q_{r} = 1/ n

D (p, q) = lo g_{2} n - H (p)

H (p) \leq lo g_{2} n

, with equality precisely for the uniform law.

 New to topics? Read the docs here!