Past exam of the mathematics course of the University of Cambridge / 2015 / iii / Paper 13 / 2 / ii

Table of contents
- Solution ii

Solution

An elementary union-intersection compression replaces two occurrences

A_{1}, A_{2}

in a multiset by

A_{1} \cup A_{2}, A_{1} \cap A_{2}

. By entropy submodularity, this changes the sum of information entropies by

H (X_{A_{1} \cup A_{2}}) + H (X_{A_{1} \cap A_{2}}) - H (X_{A_{1}}) - H (X_{A_{2}}) \leq 0.

A compression of an entropy sum is obtained by iterating these elementary union-intersection compressions. Summing the inequalities over the sequence, with repetitions counted according to their multiset multiplicities, proves the required monotonicity:

A \in A \sum H (X_{A}) \geq B \in B \sum H (X_{B}) .

Neither the number of occurrences of an individual coordinate nor the total number of sets changes under union-intersection compression.

 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