Die Entropie einer verrauschten Verteilung

9

Angenommen, wir haben eine Funktion so dass und ist eine Verteilung, dh .x Z n 2f:Z2nRfxZ n 2 f(x)=1

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

Die Shannon-Entropie von ist wie folgt definiert: H ( f ) = - x Z n 2 f ( x ) log ( f ( x ) ) .f

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

Sei eine Konstante. Angenommen, wir erhalten eine noisy-Version von , dh wir erhalten eine Funktion so dass für jedes . Wie wirkt sich das Rauschen auf die Entropie aus? Das heißt, können wir durch eine "vernünftige" Funktion von und binden , wie zum Beispiel: oder sogar für einige Konstanten .ϵ 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

Bearbeiten: Um ein Gefühl für die Auswirkung von Rauschen auf Shannons Entropie zu bekommen, wäre auch jedes "vernünftige" Additiv, das an gebunden ist , sehr interessant.H(f~)


quelle

Antworten:

8

Eine solche Bindung ist nicht möglich. Betrachten wir den Fall , wo die Verteilung ist , die gleichförmig über einen Teil Satz der Größe , und lassen die Verteilung sein , dass mit einer Wahrscheinlichkeit gibt ein gleichmäßig verteiltes Element von , und gibt ansonsten eine gleichmäßig verteilte Zeichenfolge aus.fS2δnf~δS

Es ist nicht schwer zu erkennen, dass Sie von nach Sie benötigen nur Rauschen von höchstens . Jedoch , während . Somit erhalten Sie eine Differenz von für ein beliebig kleines für ein extrem geringes Rauschen.˜ fff~ H ( f ) = δ n H ( ˜ f ) ( 1 - δ + δ 2 ) n ( 1 - δ ) 2n δ(1δ)2δnH(f)=δnH(f~)(1δ+δ2)n(1δ)2nδ

Insbesondere können Sie und Rausch und Entropiedifferenz . εn-2log(1/ε)δ=log(1/ε)nεn2log(1/ε)

Oder Meir
quelle
1
ϵn
Danke für die Korrektur. Ich weiß nicht, was die Antwort für eine additive Bindung ist.
Oder Meir
0
@DanaMoshkovitz - Der Fall einer additiven Bindung ist in der Tat sehr relevant. Ich werde es der Frage hinzufügen. Vielen Dank für den Hinweis!
H(f)0H(f)0