Desigualdad de Shearer - Enciclopedia
La desigualdad de Shearer o también el lema de Shearer, en matemáticas, es una desigualdad en la teoría de la información que relaciona la entropía de un conjunto de variables con la entropía de una colección de subconjuntos. Se nombra en honor al matemático James B. Shearer.
Concretamente, establece que si X1, ..., Xd son variables aleatorias y S1, ..., Sn son subconjuntos de {1, 2, ..., d} tales que cada entero entre 1 y d pertenece a al menos r de estos subconjuntos, entonces
H
[
(
X
1
,
…
,
X
d
)
]
≤
1
r
∑
i
=
1
n
H
[
(
X
j
)
j
∈
S
i
]
{\displaystyle H[(X_{1},\dots ,X_{d})]\leq {\frac {1}{r}}\sum _{i=1}^{n}H[(X_{j})_{j\in S_{i}}]}
donde
H
{\displaystyle H}
es la entropía y
(
X
j
)
j
∈
S
i
{\displaystyle (X_{j})_{j\in S_{i}}}
es el producto cartesiano de variables aleatorias
X
j
{\displaystyle X_{j}}
con índices j en
S
i
{\displaystyle S_{i}}
.
La desigualdad generaliza la propiedad subaditiva de la entropía, que se puede recuperar tomando
S
i
=
{
i
}
{\displaystyle S_{i}=\{i\}}
para
i
∈
{
1
,
…
,
n
}
{\displaystyle i\in \{1,\ldots ,n\}}
.
Versión combinatorial
Sea
F
{\displaystyle {\mathcal {F}}}
una familia de subconjuntos de [n] (posiblemente con repeticiones) con cada
i
∈
[
n
]
{\displaystyle i\in [n]}
incluido en al menos
t
{\displaystyle t}
miembros de
F
{\displaystyle {\mathcal {F}}}
. Sea
A
{\displaystyle {\mathcal {A}}}
otra colección de subconjuntos de
[
n
]
{\displaystyle [n]}
. Entonces
|
A
|
≤
∏
F
∈
F
|
trace
F
(
A
)
|
1
/
t
{\displaystyle {\mathcal {|}}{\mathcal {A}}|\leq \prod _{F\in {\mathcal {F}}}|\operatorname {trace} _{F}({\mathcal {A}})|^{1/t}}
donde
trace
F
(
A
)
=
{
A
∩
F
:
A
∈
A
}
{\displaystyle \operatorname {trace} _{F}({\mathcal {A}})=\{A\cap F:A\in {\mathcal {A}}\}}
es el conjunto de posibles intersecciones de elementos de
A
{\displaystyle {\mathcal {A}}}
con
F
{\displaystyle F}
.
Ver también
Lema local de Lovász
Referencias