 Solution

ID: past-exam-of-the-communication-theory-course-of-the-university-of-oxford/2009/1/b/i/solution

Factoring a joint probability into successive conditional probabilities and taking the expected negative logarithm gives the chain rule for entropy:

H_{n} = \sum_{r = 1}^{n} H (X_{r} ∣ X_{1}, \dots, X_{r - 1}) .

r = 1

this means the unconditional entropy. Removing conditioning can only increase each term by part (a), so

H_{n} \leq \sum_{r} H (X_{r})

Write

X_{- r}

for the vector omitting coordinate

r

. Another application of the chain rule gives

H (X_{- r} ∣ X_{r}) = H_{n} - H (X_{r})

. Therefore

\sum_{r} H (X_{- r} ∣ X_{r}) = n H_{n} - \sum_{r} H (X_{r}) \leq (n - 1) H_{n} .

Divide by

n - 1 > 0

to obtain the required averaged inequality. The case

n = 1

is excluded precisely because that denominator vanishes.

 New to topics? Read the docs here!