 Solution

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

X_{r}

placed last, gives

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

Since

X_{- r}

includes all the preceding coordinates, conditioning monotonicity gives

H (X_{r} ∣ X_{- r}) \leq H (X_{r} ∣ X_{1}, \dots, X_{r - 1}) .

This proves the first assertion for every

r

, including

r = 1

. Sum over

r

: the conditional terms on the right sum to

H_{n}

by the ordinary chain rule. Thus

n H_{n} \leq \sum_{r} H (X_{- r}) + H_{n}, H_{n} \leq \frac{1}{n - 1} r \sum H (X_{- r}) .

 New to topics? Read the docs here!