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

Table of contents
- Solution c

Solution

Relabel the symbols so

p_{1} \geq \dots \geq p_{m}

and assign all finite binary strings in nondecreasing length order, beginning with the empty string. The

i

th string has length

L (i) = ⌊ lo g_{2} i ⌋ .

Since

1 \geq \sum_{j = 1}^{i} p_{j} \geq i p_{i}

,

L (i) \leq lo g_{2} i \leq lo g_{2} (1/ p_{i}) .

Thus the optimal one-to-one binary code satisfies

E [L (X)] \leq i \sum p_{i} lo g_{2} (1/ p_{i}) = H (X) .

 Ancestors (10)

 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