Shearer's inequality

From Wikipedia the free encyclopedia

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