The Exercise

An outcome $x$ in a finite set $\mathcal{X}$ is produced in two steps. First an index $i$ is drawn from a finite set $I$ with probability $p_i$; then $x$ is drawn from a probability distribution $q_i$ on $\mathcal{X}$ that depends on the index. Someone who sees only the outcome finds $x$ with probability $\sum_i p_i q_i(x)$, so the outcome follows the mixture $\sum_i p_i q_i$ of the distributions $q_i$ with weights $p_i$.

The exercise is to show that the Shannon entropy is concave: the entropy of the mixture is at least the average of the entropies of the $q_i$, taken with the weights $p_i$.^✦

The Shannon Entropy

The Shannon entropy $H(r)$ of a probability distribution $r$ on a finite set $\mathcal{X}$ is the number $$H(r) = -\sum_{x \in \mathcal{X}} r(x) \log r(x),$$(1)^✦ with the natural logarithm, so that $H$ is measured in nats.

The Claim

What Is Checked

The claim is stated over one construction, the Shannon entropy (1), taken of each $q_i$ and of their mixture. About it the library has the inequality (2), for finite sets $I$ and $\mathcal{X}$ of any size.