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

: $H[(X_1,\dots,X_d)] \leq \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}$ .{{cite journal|last1=Chung|first1=F.R.K.|last2=Graham|first2=R.L.|last3=Frankl|first3=P.|last4=Shearer|first4=J.B.|title=Some Intersection Theorems for Ordered Sets and Graphs|journal=J. Comb. Theory A|date=1986|volume=43|pages=23–37|doi=10.1016/0097-3165(86)90019-1|doi-access=free}}

Combinatorial version

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

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

where $\operatorname{trace}_{F}(\mathcal{A})=\{A\cap F:A\in\mathcal{A}\}$ the set of possible intersections of elements of $\mathcal{A}$ with $F$ .{{cite arXiv|last=Galvin|first=David|date=2014-06-30|title=Three tutorial lectures on entropy and counting|class=math.CO|eprint=1406.7872}}

References

Category:Information theory

Category:Inequalities (mathematics)

Shearer's inequality

Combinatorial version

See also

References