Desigualdad de Shearer

La desigualdad de Shearer o también lema de Shearer, en matemáticas , es una desigualdad de la teoría de la información que relaciona la entropía de un conjunto de variables con las entropías de una colección de subconjuntos. Recibe su nombre en honor al matemático James B. Shearer.

Concretamente, establece que si X ₁ , ...,  X _d son variables aleatorias y S ₁ , ...,  S _n son subconjuntos de {1, 2, ...,  d } tales que todo entero entre 1 y d se encuentra en al menos r de estos subconjuntos, entonces

${\displaystyle H[(X_{1},\puntos ,X_{d})]\leq {\frac {1}{r}}\sum _{i=1}^{n}H[(X_{j})_{j\in S_{i}}]}$

donde es la entropía y es el producto cartesiano de variables aleatorias con índices j en . ^[1]${\estilo de visualización H}$${\displaystyle (X_{j})_{j\in S_{i}}}$$Estilo de visualización X_ {j}}$$Estilo de visualización S_{i}}$

Sea una familia de subconjuntos de [n] (posiblemente con repeticiones) con cada uno incluido en al menos miembros de . Sea otro conjunto de subconjuntos de . Entonces ${\displaystyle {\mathcal {F}}}$${\displaystyle i\in [n]}$${\estilo de visualización t}$${\displaystyle {\mathcal {F}}}$${\displaystyle {\mathcal {A}}}$${\estilo de visualización [n]}$

${\displaystyle {\mathcal {|}}{\mathcal {A}}|\leq \prod _{F\in {\mathcal {F}}}|\operatorname {traza} _{F}({\mathcal {A}})|^{1/t}}$

donde el conjunto de posibles intersecciones de elementos de con . ^[2]${\displaystyle \operatorname {traza} _{F}({\mathcal {A}})=\{A\cap F:A\in {\mathcal {A}}\}}$${\displaystyle {\mathcal {A}}}$${\estilo de visualización F}$

• Lema local de Lovász