= Madiman–Tetali entropy inequality
{c}
= Madiman-Tetali inequality
{c}
{synonym}
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_AH(X_A\mid X_{A^+})\leq kH(X)\leq\sum_AH(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 https://arxiv.org/abs/0901.0044[Madiman and Tetali, "Information Inequalities for Joint Distributions"].
Back to article page
