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)$.

A union-intersection compression can only decrease the sum of information entropies ${\sum }_{A\in \mathcal{A}}H(X_A)$ for a finite-valued random vector $X$. Each elementary step follows from entropy submodularity; iteration proves the assertion with multiset multiplicities. Uniform coordinate multiplicity gives Shearer inequality by compressing to repeated full sets and empty sets.

Let $\mathcal{A}$ be a finite multiset of subsets and let $r_i$ count its occurrences of coordinate $i$. Its nested compression consists of $L_j=\{i:r_i\ge j\}$. Then ${\sum }_{j}H(X_{L_j})\le {\sum }_{A\in \mathcal{A}}H(X_A)$, by repeated entropy submodularity. This is the compression formulation in Balister and Bollobás, "Projections, Entropy and Sumsets".

For a nonempty ordered coordinate set $A$, write $A^{-}=[\min A-1]$ and $A^{+}=[\max A-1]\setminus A$. An exact $k$-cover satisfies ${\sum }_{A}H(X_A\mid X_{A^{+}})\le kH(X)\le {\sum }_{A}H(X_A\mid X_{A^{-}})$. A short proof uses the chain rule for information entropy contributions $h_i=H(X_i\mid X_{[i-1]})$: each conditional subset entropy bounds ${\sum }_{i\in A}{h}_i$ on the appropriate side, by conditioning reduces entropy. Weighting gives the lower inequality for a fractional packing and the upper inequality for a fractional cover. See Madiman and Tetali, "Information Inequalities for Joint Distributions".

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.

If every pair of graphs in a family on $[n]$ has a graph intersection without an isolated vertex, the family has at most $2^{n(n-2)/2}$ members. At each vertex, its possible graph neighbourhoods form an intersecting family, of size at most $2^{n-2}$. Every edge occurs in two such neighbourhood projections. Shearer inequality bounds twice the full information entropy by the sum of their information entropies.