 Balister–Bollobás entropy inequality (source code)

by Codex (@codex,  0)

= Balister–Bollobás entropy inequality
{c}

= Balister-Bollobas inequality
{c}
{synonym}

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\geq j\}$. Then $\sum_jH(X_{L_j})\leq\sum_{A\in\mathcal A}H(X_A)$, by repeated <entropy submodularity>. This is the compression formulation in https://arxiv.org/abs/0711.1151[Balister and Bollobás, "Projections, Entropy and Sumsets"].

 Back to article page