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}$ .[1]

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

References

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.
Galvin, David (2014-06-30). "Three tutorial lectures on entropy and counting". arXiv:1406.7872 [math.CO].

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[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 [math.CO].

Shearer's inequality

Combinatorial version

See also

References