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 .[1]

Combinatorial version

edit

Let   be a family of subsets of [n] (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  .[2]

See also

edit

References

edit
  1. ^ Chung, F.R.K.; Graham, R.L.; Frankl, P.; Shearer, J.B. (1986). "Some Intersection Theorems for Ordered Sets and Graphs". J. Comb. Theory A. 43: 23–37. doi:10.1016/0097-3165(86)90019-1.
  2. ^ Galvin, David (2014-06-30). "Three tutorial lectures on entropy and counting". arXiv:1406.7872 [math.CO].