En la entropía de una suma

12

Estoy en busca de una cota en la entropía de la suma de dos variables aleatorias discretas independientes X y Y . Naturalmente, H ( X + Y ) H ( X ) + H ( Y ) ( ) Sin embargo, aplicado a la suma de n variables aleatorias independientes de Bernoulli Z 1 , ... , Z n , esto da H ( Z 1 +H(X+Y)XY

H(X+Y)H(X)+H(Y)      ()
nZ1,,Zn En otras palabras, el límite crece linealmente con n cuando se aplica repetidamente. Sin embargo, Z 1 + Z n es compatible con un conjunto de tamaño n , por lo que su entropía es como máximo log n . De hecho, por el teorema del límite central, supongo que H ( Z 1 + + Z n ) ( 1 / 2 ) log
H(Z1+Z2++Zn)nH(Z1)
nZ1+Znnlogn ya que es esencialmente compatible con un conjunto de tamañoH(Z1++Zn)(1/2)logn .n

En resumen, el límite sobrepasa bastante en esta situación. Al leer esta publicación de blog , deduzco que son posibles todo tipo de límites en H ( X + Y ) ; ¿Hay un límite que proporcione los asintóticos correctos (o, al menos, los asintóticos más razonables) cuando se aplican repetidamente a la suma de variables aleatorias de Bernoulli?()H(X+Y)

Robinson
fuente
2
No estoy seguro de lo que realmente estás preguntando. Si desea un límite superior en H (X + Y) en términos de H (X) y H (Y) que se aplica a cualquiera de las dos variables aleatorias discretas independientes X e Y, entonces H (X + Y) ≤H (X ) + H (Y) es claramente lo mejor que puede obtener; considere el caso donde las sumas x + y son todas distintas cuando x se extiende sobre el soporte de X e y se extiende sobre el soporte de Y. Si aplica este límite general a un caso muy especial, entonces es natural que obtenga un muy atado suelto
Tsuyoshi Ito
1
H(X+Y)H(X)+H(Y)n
1
H(X+Y)3H(XY)H(X)H(Y)
2
Eso significa que lo que está buscando no es un límite superior en H (X + Y) en términos de H (X) y H (Y) . Por favor edite la pregunta.
Tsuyoshi Ito
1
Zin

Respuestas:

19

XA2H(X)YB2H(Y)

|A+B||A||B||A+B||A||B|H(X+Y)H(X)+H(Y)

|A+B||A||B|AB|A+B|(G,+)|A+B|=O(|A|+|B|)A,BG

A[a..b]B[0..c](1/2)lognc=1a=0b=kk=1,...,n1akkbk+k|A+B||A|+c

Boaz Barak
fuente
5

nZ1,Z2,...,ZnpZ1+Z2+...+Znnpnp12logn+O(logn)

VSJ
fuente
0

Tal vez podrías usar la ecuación:

H(Z1+Z2++Zn)=H(Z1)+H(Z2)++H(Zn)H(Z1|Z1+Z2++Zn)H(Z2|Z2+Z3++Zn)H(Zn1|Zn1+Zn)

Esto parecería un término que usted mencionó en los comentarios, desafortunadamente no conozco los resultados sobre la cardinalidad de los términos negativos o los límites perspicaces sobre ellos.

Almiar
fuente