Misplaced Pages

This article may be too technical for most readers to understand. Please help improve it to make it understandable to non-experts, without removing the technical details. (December 2021) (Learn how and when to remove this message)

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\leq {\frac {1}{r}}\sum _{i=1}^{n}H}$

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}}$.

Combinatorial version

Let ${\displaystyle {\mathcal {F}}}$ be a family of subsets of (possibly with repeats) with each ${\displaystyle i\in }$ included in at least ${\displaystyle t}$ members of ${\displaystyle {\mathcal {F}}}$. Let ${\displaystyle {\mathcal {A}}}$ be another set of subsets of ${\displaystyle }$. 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}$.

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 .

• Information theory
• Inequalities