Shearer's inequality
From Wikipedia, the free encyclopedia
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 {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}}]}](http://wikimedia.org/api/rest_v1/media/math/render/svg/c2c3e4d18aa93d1dffaa7c5525d9f248c4b4ce9f)
where is entropy and is the Cartesian product of random variables with indices j in .[1]
The inequality generalizes the subadditivity property of entropy, which can be recovered by taking for .[2]
Combinatorial version
Let be a family of subsets of (possibly with repeats) with each included in at least members of . Let be another set of subsets of . Then
![{\displaystyle [n]}](http://wikimedia.org/api/rest_v1/media/math/render/svg/a26847bfc29bbeb4d6ef62ac3fd076378c0fd1db)
![{\displaystyle i\in [n]}](http://wikimedia.org/api/rest_v1/media/math/render/svg/1b389a8f1ad8a43d2bcf5194acf34e934f806311)
where the set of possible intersections of elements of with .[2]
