HOME

TheInfoList



OR:

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''1, ..., ''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''1, ..., ''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.


See also

*
Lovász local lemma In probability theory, if a large number of events are all independent of one another and each has probability less than 1, then there is a positive (possibly small) probability that none of the events will occur. The Lovász local lemma allows on ...


References

{{DEFAULTSORT:Shearer's Inequality Information theory Inequalities