 Solution

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

Use the continuous convention

0 lo g_{2} (0/ q) = 0

. Let

S = {r : p_{r} > 0}

. Applying the allowed logarithm inequality to

q_{r} / p_{r}

for

r \in S

gives

- d (p, q) = \sum_{r \in S} p_{r} lo g_{2} \frac{q _{r}}{p _{r}} \leq c \sum_{r \in S} (q_{r} - p_{r}) = c (\sum_{r \in S} q_{r} - 1) \leq 0.

Hence

d (p, q) \geq 0

\sum_{r \in S} q_{r} = 1

. Since every

q_{r}

is strictly positive, this makes

S

q_{r} / p_{r} = 1

for every

r

. Conversely

p = q

makes every summand zero. Thus

d (p, q) \geq 0, d (p, q) = 0 ⟺ p = q .

This is Gibbs inequality for relative entropy, with zero probabilities in the first argument handled explicitly.

 New to topics? Read the docs here!