Madiman–Tetali entropy inequality

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".