Shearer's inequality

From Wikipedia, the free encyclopedia
Jump to: navigation, search

In information theory, Shearer's inequality 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 exactly 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  (X_{j})_{j\in S_{i}} is the Cartesian product of random variables X_{j} with indices j in S_{i} (so the dimension of this vector is equal to the size of S_{i}).