Pada entropi jumlah

12

Saya mencari terikat pada entropi dari jumlah dari dua variabel acak diskrit independen X dan Y . Tentu, H ( X + Y ) H ( X ) + H ( Y ) ( * ) Namun, diterapkan dengan jumlah dari n independen Bernoulli variabel acak Z 1 , ... , Z n , ini memberikan H ( Z 1 +H(X+Y)XY

H(X+Y)H(X)+H(Y)      ()
nZ1,,Zn Dengan kata lain, batas tumbuh secara linier dengan n ketika diterapkan berulang kali. Namun, Z 1 + Z n didukung pada serangkaian ukuran n , sehingga entropinya paling banyak adalah log n . Bahkan, dengan teorema limit sentral, aku menduga bahwa H ( Z 1 + + Z n ) ( 1 / 2 ) log
H(Z1+Z2++Zn)nH(Z1)
nZ1+Znnlogn karena pada dasarnya didukung pada set ukuranH(Z1++Zn)(1/2)logn .n

Singkatnya, batas dilampaui oleh sedikit dalam situasi ini. Dari membaca dengan teliti posting blog ini , saya mengumpulkan segala macam batasan pada H ( X + Y ) adalah mungkin; apakah ada batasan yang memberikan asimptotik yang tepat (atau, paling tidak, asimptotik yang lebih masuk akal) ketika diterapkan berulang kali pada jumlah variabel acak Bernoulli?()H(X+Y)

Robinson
sumber
2
Saya tidak yakin apa yang sebenarnya Anda tanyakan. Jika Anda ingin batas atas H (X + Y) dalam hal H (X) dan H (Y) yang berlaku untuk dua variabel acak diskrit independen X dan Y, maka H (X + Y) ≤H (X ) + H (Y) jelas yang terbaik yang bisa Anda dapatkan; pertimbangkan kasus di mana jumlah x + y semuanya berbeda ketika x berkisar di atas dukungan X dan y berkisar di atas dukungan dari Y. Jika Anda menerapkan ikatan umum ini ke kasus yang sangat khusus, maka wajar jika Anda mendapatkan terikat longgar.
Tsuyoshi Ito
1
H(X+Y)H(X)+H(Y)n
1
H(X+Y)3H(XY)H(X)H(Y)
2
Itu berarti bahwa apa yang Anda cari bukanlah batas atas H (X + Y) dalam hal H (X) dan H (Y) . Harap edit pertanyaan.
Tsuyoshi Ito
1
Zin

Jawaban:

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

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

VSJ
sumber
0

Mungkin Anda bisa menggunakan Persamaan:

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

Ini akan terlihat seperti istilah yang Anda sebutkan di komentar, sayangnya saya tidak tahu hasil tentang kardinalitas istilah negatif atau batasan wawasan pada mereka.

Rick
sumber