Shearer's inequality

Template:Technical 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

$H[(X_1,\dots ,X_d)]\le \frac{1}{r}\sum _{i=1}^{n}H[(X_j{)}_{j\in S_i}]$

where $H$ is entropy and $(X_j{)}_{j\in S_i}$ is the Cartesian product of random variables $X_j$ with indices j in $S_i$.

Combinatorial version

Let $ℱ$ be a family of subsets of [n] (possibly with repeats) with each $i\in [n]$ included in at least $t$ members of $ℱ$. Let $𝒜$ be another set of subsets of $[n]$. Then

$\mathcal{|}𝒜|\le \prod _{F\in ℱ}|{\mathrm{trace}}_F(𝒜){|}^{1/t}$

where ${\mathrm{trace}}_F(𝒜)=\{A\cap F:A\in 𝒜\}$ the set of possible intersections of elements of $𝒜$ with $F$.

See also

• Lovász local lemma