Entropy submodularity

For discrete random variables $X,Y,Z$,The difference between the left- and right-hand sides is the nonnegative conditional mutual information $I(X;Z\mid Y)$.

Let $X=(X_1,\dots ,X_n)$ be a discrete random vector, and let $\mathcal{S}$ be a collection of subsets of $[n]$ in which every index occurs at least $r$ times. ThenApply the chain rule for information entropy to each projection $X_S$ and use conditioning reduces entropy to compare every term with the corresponding conditional entropy in the full chain rule.