= 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})\leq0.
$$
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 \b[the required monotonicity]:
$$
\boxed{\sum_{A\in\mathcal A}H(X_A)\geq\sum_{B\in\mathcal B}H(X_B).}
$$
Neither the number of occurrences of an individual coordinate nor the total number of sets changes under <union-intersection compression>.
Back to article page
