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 X1, ..., Xd are random variables and S1, ..., Sn 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 , … , X d ) ] ≤ 1 r ∑ i = 1 n H [ ( X j ) j ∈ S i ] {\displaystyle H[(X_{1},\dots ,X_{d})]\leq {\frac {1}{r}}\sum _{i=1}^{n}H[(X_{j})_{j\in S_{i}}]}
where H {\displaystyle H} is entropy and ( X j ) j ∈ S i {\displaystyle (X_{j})_{j\in S_{i}}} is the Cartesian product of random variables X j {\displaystyle X_{j}} with indices j in S i {\displaystyle S_{i}} . The inequality generalizes the subadditivity property of entropy, which can be recovered by taking S i = { i } {\displaystyle S_{i}=\{i\}} for i ∈ { 1 , … , n } {\displaystyle i\in \{1,\ldots ,n\}} .
Combinatorial version Let F {\displaystyle {\mathcal {F}}} be a family of subsets of [ n ] {\displaystyle [n]} (possibly with repeats) with each i ∈ [ n ] {\displaystyle i\in [n]} included in at least t {\displaystyle t} members of F {\displaystyle {\mathcal {F}}} . Let A {\displaystyle {\mathcal {A}}} be another set of subsets of [ n ] {\displaystyle [n]} . Then
| A | ≤ ∏ F ∈ F | trace F ( A ) | 1 / t {\displaystyle {\mathcal {|}}{\mathcal {A}}|\leq \prod _{F\in {\mathcal {F}}}|\operatorname {trace} _{F}({\mathcal {A}})|^{1/t}}
where trace F ( A ) = { A ∩ F : A ∈ A } {\displaystyle \operatorname {trace} _{F}({\mathcal {A}})=\{A\cap F:A\in {\mathcal {A}}\}} the set of possible intersections of elements of A {\displaystyle {\mathcal {A}}} with F {\displaystyle F} .
See also Lovász local lemma
References