Jump to content

Shearer's inequality

From Wikipedia, the free encyclopedia
(Redirected from Sheerer'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 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].