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 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

be a family of subsets of [n] (possibly with repeats) with each

be another set of subsets of

trace

{\displaystyle \operatorname {trace} _{F}({\mathcal {A}})=\{A\cap F:A\in {\mathcal {A}}\}}

the set of possible intersections of elements of