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 X₁, ..., X_d are random variables and S₁, ..., S_n are subsets of {1, 2, ..., d} such that every integer between 1 and d lies in at least r of these subsets, then

${\displaystyle H[(X_{1},\dots ,X_{d})]\leq {\frac {1}{r}}\sum _{i=1}^{n}H[(X_{j})_{j\in S_{i}}]}$

where ${\displaystyle H}$ is entropy and ${\displaystyle (X_{j})_{j\in S_{i}}}$ is the Cartesian product of random variables ${\displaystyle X_{j}}$ with indices j in ${\displaystyle S_{i}}$.[1]

Combinatorial version

Let ${\displaystyle {\mathcal {F}}}$ be a family of subsets of [n] (possibly with repeats) with each ${\displaystyle i\in [n]}$ included in at least ${\displaystyle t}$ members of ${\displaystyle {\mathcal {F}}}$. Let ${\displaystyle {\mathcal {A}}}$ be another set of subsets of ${\displaystyle [n]}$. Then

${\displaystyle {\mathcal {|}}{\mathcal {A}}|\leq \prod _{F\in {\mathcal {F}}}|\operatorname {trace} _{F}({\mathcal {A}})|^{1/t}}$

where ${\displaystyle \operatorname {trace} _{F}({\mathcal {A}})=\{A\cap F:A\in {\mathcal {A}}\}}$ the set of possible intersections of elements of ${\displaystyle {\mathcal {A}}}$ with ${\displaystyle F}$.[2]

See also

• Lovász local lemma

References

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