Past exam of the mathematics course of the University of Cambridge / 2026 / iii / Paper 224 / 4 / c / Solution

Monotonicity of the ordered probabilities gives

i p_{i} \leq \sum_{j \leq i} p_{j} \leq 1

, so

lo g i \leq - lo g p_{i}

. Consequently

E [L^{*} (X)] = \sum_{i} p_{i} ⌊ lo g i ⌋ \leq \sum_{i} p_{i} lo g i \leq H (X) .

Given

L^{*} (X) = l

, the source symbol can take at most

2^{l}

values. The maximum entropy distribution on a finite set is uniform, hence

H (X ∣ L^{*} (X) = l) \leq lo g 2^{l} = l .

Averaging this conditional entropy inequality proves

H (X ∣ L^{*} (X)) \leq E [L^{*} (X)] .

 Ancestors (11)

 View article source

 Discussion (0)

There are no discussions about this article yet.

 Articles by others on the same topic (0)

There are currently no matching articles.

  See all articles in the same topic Create my own version