 Solution

ID: past-exam-of-the-communication-theory-course-of-the-university-of-oxford/2008/2/a/solution

H (X) = - \sum_{p_{i} > 0} p_{i} lo g_{2} p_{i},

with

0 lo g_{2} 0 = 0

. If the positive support has size

s \leq n

Z = 1/ p_{X}

H (X) = E lo g_{2} Z \leq lo g_{2} E Z = lo g_{2} s \leq lo g_{2} n .

Equality requires

s = n

and

Z

1/ n

. Conversely the uniform distribution attains this bound. Thus

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

, with exactly that equality case.

 New to topics? Read the docs here!