Shearer's inequality or also Shearer's lemma, in mathematics, is an inequality in

information theory Information theory is the scientific study of the quantification, storage, and communication of information. The field was originally established by the works of Harry Nyquist and Ralph Hartley, in the 1920s, and Claude Shannon in the 1940s. ...

relating the

entropy Entropy is a scientific concept, as well as a measurable physical property, that is most commonly associated with a state of disorder, randomness, or uncertainty. The term and the concept are used in diverse fields, from classical thermodyna ...

of a set of variables to the entropies of a collection of subsets. It is named for mathematician

James B. Shearer James is a common English language surname and given name: * James (name), the typically masculine first name James * James (surname), various people with the last name James James or James City may also refer to: People * King James (disambigua ...

. Concretely, it states that if ''X''₁, ..., ''X''_''d'' are

random variable A random variable (also called random quantity, aleatory variable, or stochastic variable) is a mathematical formalization of a quantity or object which depends on random events. It is a mapping or a function from possible outcomes (e.g., the p ...

s and ''S''₁, ..., ''S''_''n'' are subsets of 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\sum_^n H X_j)_/math>

where H is entropy and (X_)_is the

Cartesian product In mathematics, specifically set theory, the Cartesian product of two sets ''A'' and ''B'', denoted ''A''×''B'', is the set of all ordered pairs where ''a'' is in ''A'' and ''b'' is in ''B''. In terms of set-builder notation, that is : A\ ...

of random variables

X_

with indices ''j'' in

S_

Combinatorial version

Let

\mathcal

be a family of subsets of (possibly with repeats) with each

i\in /math> included in at least t members of \mathcal . Let \mathcal be another set of subsets of \mathcal F . Then \mathcal , \mathcal, \leq \prod_\operatorname_(\mathcal)^where \operatorname_(\mathcal)=\ the set of possible intersections of elements of \mathcal with F .

References

{{DEFAULTSORT:Shearer's Inequality Information theory Inequalities

Combinatorial version

See also

References