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

[math]\displaystyle{ H[(X_1,\dots,X_d)] \leq \frac{1}{r}\sum_{i=1}^n H[(X_j)_{j\in S_i}] }[/math]

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

Combinatorial version

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

[math]\displaystyle{ \mathcal |\mathcal{A}|\leq \prod_{F\in \mathcal{F}}\operatorname{trace}_{F}(\mathcal{A})^{1/t} }[/math]

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

See also

• Lovász local lemma