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
where is entropy and is the Cartesian product of random variables with indices j in .
The inequality generalizes the subadditivity property of entropy, which can be recovered by taking for .
Combinatorial version Let be a family of subsets of (possibly with repeats) with each included in at least members of . Let be another set of subsets of . Then
where the set of possible intersections of elements of with .
See also
Lovász local lemma
References