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 {\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

• Lovász local lemma

References

This page was last edited on 18 September 2023, at 17:44