Shearer's inequality

Shearer's inequality or also Shearer's lemma, in mathematics, is an inequality in information theory relating the entropy of a set of variables to the entropies of a collection of subsets. It is named for mathematician James B. Shearer.

Concretely, it states that if X₁, ..., X_d are random variables and S₁, ..., S_n are subsets of {1, 2, ..., d} such that every integer between 1 and d lies in at least r of these subsets, then

$H[(X_{1},\dots ,X_{d})]\leq {\frac {1}{r}}\sum _{i=1}^{n}H[(X_{j})_{j\in S_{i}}]$

where $H$ is entropy and $(X_{j})_{j\in S_{i}}$ is the Cartesian product of random variables $X_{j}$ with indices j in $S_{i}$.

Combinatorial version

Let ${\mathcal {F}}$ be a family of subsets of [n] (possibly with repeats) with each $i\in [n]$ included in at least $t$ members of ${\mathcal {F}}$. Let ${\mathcal {A}}$ be another set of subsets of ${\mathcal {F}}$. Then

${\mathcal {|}}{\mathcal {A}}|\leq \prod _{F\in {\mathcal {F}}}\operatorname {trace} _{F}({\mathcal {A}})^{1/t}$

where $\operatorname {trace} _{F}({\mathcal {A}})=\{A\cap F:A\in {\mathcal {A}}\}$ the set of possible intersections of elements of ${\mathcal {A}}$ with $F$.

See also

• Lovász local lemma