La entropía de una distribución ruidosa.

9

Digamos que tenemos una función tal que x Z n 2f:Z2nR yfes una distribución, es decir,ΣxZ n 2 f(x)=1.

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

La entropía de Shannon de se define como sigue: H ( f ) = - x Z n 2 f ( x ) log ( f ( x ) ) .f

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

Deje ser algo constante. Digamos que obtenemos una versión ϵ- ruidosa de f ( x ) , es decir, obtenemos una función ˜ f : Z n 2R tal que | ~ F ( x ) - f ( x ) | < ϵ por cada x Z n 2 . ¿Cuál es el efecto del ruido en la entropía? Esto es, podemos obligados H ( ~ f ) por una función de "razonable" de εϵϵf(x)f~:Z2nR|f~(x)f(x)|<ϵxZ2nH(f~)ϵy , como: ( 1 - ϵ ) H ( f ) < H ( ˜ f ) < ( 1 + ϵ ) H ( f ) , o incluso, ( 1 - ϵ c n ) d H ( f ) < H ( ˜ f ) < ( 1 + ϵ c n )H(f)

(1ϵ)H(f)<H(f~)<(1+ϵ)H(f),
para algunas constantes c , d .
(1ϵcn)dH(f)<H(f~)<(1+ϵcn)dH(f),
c,d

Editar: Tratando de conseguir una sensación para el efecto del ruido sobre la entropía de Shannon, cualquier aditivo "razonable" Límite en también sería muy interesante.H(f~)


fuente

Respuestas:

8

fS2δnf~δS

ff~(1δ)2δnH(f)=δnH(f~)(1δ+δ2)n(1δ)2nδ

δ=log(1/ε)nεn2log(1/ε)

O meir
fuente
1
ϵn
Gracias por la corrección. No sé cuál es la respuesta para un enlace aditivo.
O Meir el
0
@DanaMoshkovitz: el caso de un enlace aditivo es realmente muy relevante. Lo agregaré a la pregunta. ¡Gracias por mencionarlo!
H(f)0H(f)0