Na entropia de uma soma

12

Eu estou procurando um ligado na entropia da soma de duas variáveis aleatórias discretas independentes X e Y . Naturalmente, H ( X + Y ) H ( X ) + H ( Y ) ( ) No entanto, aplicado à soma de n variáveis ​​aleatórias independentes Bernoulli Z 1 , , Z n , isso dá H ( Z 1 +H(X+Y)XY

H(X+Y)H(X)+H(Y)      ()
nZ1,,Zn Em outras palavras, o limite cresce linearmente com n quando aplicado repetidamente. No entanto, Z 1 + Z n é suportado em um conjunto de tamanho n , portanto sua entropia é no máximo log n . Na verdade, pelo teorema limite central, acredito que H ( Z 1 + + Z n ) ( 1 / 2 ) de registo
H(Z1+Z2++Zn)nH(Z1)
nZ1+Znnlogn já que é essencialmente suportado em um conjunto de tamanhoH(Z1++Zn)(1/2)logn .n

Em resumo, o limite ultrapassa um pouco nessa situação. Ao ler esta publicação no blog , eu entendo todos os tipos de limites em H ( X + Y ) são possíveis; existe um limite que dê os assintóticos corretos (ou, pelo menos, assintóticos mais razoáveis) quando aplicado repetidamente à soma das variáveis ​​aleatórias de Bernoulli?()H(X+Y)

Robinson
fonte
2
Não sei ao certo o que você está realmente perguntando. Se você deseja um limite superior em H (X + Y) em termos de H (X) e H (Y) aplicável a quaisquer duas variáveis ​​aleatórias discretas independentes X e Y, então H (X + Y) ≤H (X ) + H (Y) é claramente o melhor que você pode obter; considere o caso em que as somas x + y são todas distintas quando x varia sobre o suporte de X e y sobre o suporte de Y. Se você aplicar esse limite geral a um caso muito especial, é natural que você obtenha uma limite solto.
Tsuyoshi Ito
1
H(X+Y)H(X)+H(Y)n
1
H(X+Y)3H(XY)H(X)H(Y)
2
Isso significa que o que você está procurando não é um limite superior em H (X + Y) em termos de H (X) e H (Y) . Por favor edite a pergunta.
Tsuyoshi Ito
1
Zin

Respostas:

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
fonte
5

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

VSJ
fonte
0

Talvez você possa usar a equação:

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

Parece um termo que você mencionou nos comentários, infelizmente não conheço resultados sobre a cardinalidade dos termos negativos ou limites perspicazes sobre eles.

Rick
fonte