Entropi dari distribusi yang bising

9

Katakanlah kita memiliki fungsi sedemikian rupa sehingga dan adalah distribusi, yaitu, .x Z n 2f:Z2nRfxZ n 2 f(x)=1

xZ2nf(x){12n,22n,,2n2n},
fxZ2nf(x)=1

Entropi Shannon dari didefinisikan sebagai berikut: H ( f ) = - x Z n 2 f ( x ) log ( f ( x ) ) .f

H(f)=xZ2nf(x)log(f(x)).

Biarkan menjadi konstan. Katakanlah kita mendapatkan versi -noisy dari , yaitu, kita mendapatkan fungsi sedemikian rupa sehingga untuk setiap . Apa efek dari kebisingan pada entropi? Yaitu, dapatkah kita mengikat dengan fungsi "wajar" dari dan , seperti: atau bahkan, untuk beberapa konstanta .ϵ f ( x ) ˜ f : Z n 2R | ˜ f ( x ) - f ( x ) | < ϵ x Z n 2 H ( ˜ f ) ϵ H ( f ) ( 1 - ϵ ) H ( f ) < H ( ˜ f ) < ( 1ϵϵf(x)f~:Z2nR|f~(x)f(x)|<ϵxZ2nH(f~)ϵH(f)

(1ϵ)H(f)<H(f~)<(1+ϵ)H(f),
(1ϵcn)dH(f)<H(f~)<(1+ϵcn)dH(f),
c,d

Sunting: Mencoba untuk merasakan efek kebisingan pada entropi Shannon, aditif "wajar" apa pun yang terikat pada juga akan sangat menarik.H(f~)


sumber

Jawaban:

8

Batas seperti itu tidak mungkin. Pertimbangkan kasus di mana adalah distribusi yang seragam pada beberapa himpunan ukuran , dan mari menjadi distribusi yang dengan probabilitas menghasilkan elemen terdistribusi secara merata , dan sebaliknya menghasilkan string yang terdistribusi secara merata.fS2δnf~δS

Tidak sulit untuk melihat bahwa Anda dapat beralih dari ke Anda hanya membutuhkan noise paling banyak . Namun, sementara . Dengan demikian, Anda mendapatkan perbedaan untuk kecil sewenang-wenang untuk noise yang sangat rendah.ff~(1δ)2δnH(f)=δnH(f~)(1δ+δ2)n(1δ)2nδ

Secara khusus, Anda dapat mengatur , dan mendapatkan noise dan perbedaan entropi .δ=log(1/ε)nεn2log(1/ε)

Atau Meir
sumber
1
Maksudmu kira - kira , kan? Bagaimanapun, saya pikir itu mungkin membantu penanya untuk menjawab tentang batas aditif juga, dan bukan hanya tentang ikatan mutliplicative (saya tahu dia bertanya secara spesifik tentang multiplicative). ϵn
Dana Moshkovitz
Terima kasih atas koreksinya. Saya tidak tahu apa jawaban untuk ikatan aditif.
Atau Meir
Terima kasih atas jawabannya Atau! Tidak ada harapan untuk mendapatkan ikatan multiplikatif pada fungsi dengan entropi . Namun, bagaimana dengan fungsi dengan entropi lebih besar dari 0? Apakah mungkin untuk mendapatkan ikatan seperti itu? 0
@DanaMoshkovitz - Kasus ikatan tambahan memang sangat relevan. Saya akan menambahkannya ke pertanyaan. Terima kasih telah menunjukkannya!
H(f)0H(f)0