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 X1, ..., Xd are random variables and S1, ..., Sn are subsets of such that every integer between 1 and d lies in at least r of these subsets, then
H[(X1,...,Xd)]\leq
| 1 | |
| r |
| n | |
| \sum | |
| i=1 |
H[(Xj)
| j\inSi |
]
where
H
(Xj
| ) | |
| j\inSi |
Xj
Si
Let
l{F}
i\in[n]
t
l{F}
l{A}
[n]
l|l{A}|\leq\prodF\in
where
\operatorname{trace}F(l{A})=\{A\capF:A\inl{A}\}
l{A}
F