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[(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 [ edit ]

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 {\mathcal {F}}}$. 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 [ edit ]

• Lovasz local lemma

References [ edit ]