A entropia de uma distribuição barulhenta

Digamos que temos uma função $f:\mathbb{Z}_2^n \to \mathbb{R}$ tal que efé uma distribuição, ou seja,∑x∈Z n 2 f(x)=1.

$$\forall x\in \mathbb{Z}_2^n \quad f(x) \in \left\{\frac{1}{2^n}, \frac{2}{2^n}, \ldots, \frac{2^n}{2^n} \right\},$$ $f$$\sum_{x\in \mathbb{Z}_2^n} f(x) = 1$

A entropia de Shannon de é definida da seguinte forma: H ( f ) = - ∑ x ∈ Z n 2 f ( x ) log ( f ( x ) )$f$

$$H(f) = -\sum _{x \in \mathbb{Z}_2^n} f(x) \log \left( f(x) \right) .$$

Deixe haver alguma constante. Digamos que temos um ε versão -Noisy de f ( x ) , ou seja, temos uma função ~ f : Z n 2 → R tal que | ˜ f ( x ) - f ( x ) | < ϵ para cada x ∈ Z n 2 . Qual é o efeito do ruído na entropia? Ou seja, podemos obrigado H ( ~ f ) por uma função de "razoável" de $\epsilon$$\epsilon$$f(x)$$\tilde{f}:\mathbb{Z}_2^n \to \mathbb{R}$$|\tilde{f}(x)- f(x) | < \epsilon$$x\in \mathbb{Z}_2^n$$H(\tilde{f})$$\epsilon$e , tais como: ( 1 - ε ) H ( f ) < H ( ~ f ) < ( 1 + ε ) H ( f ) , ou mesmo, ( 1 - ε c n ) d H ( f ) < H ( ~ f ) < ( 1 + ε c n $H(f)$

$$(1-\epsilon)H(f) < H(\tilde{f}) < (1+\epsilon)H(f),$$ para algumas constantes c , d . $$(1-\epsilon^c n)^d H(f) < H(\tilde{f}) < (1+\epsilon^c n)^d H(f),$$ $c,d$

Edit: Tentando sentir o efeito do ruído na entropia de Shannon, qualquer aditivo "razoável" ligado a também seria muito interessante.$H(\tilde{f})$

Esse limite não é possível. Considere o caso em que$f$$S$$2^{\delta \cdot n}$$\tilde{f}$$\delta$$S$

$f$$\tilde{f}$$(1-\delta) \cdot 2^{-\delta \cdot n}$$H(f)= \delta \cdot n$$H(\tilde{f}) \approx (1 - \delta + \delta^2) \cdot n$$(1 - \delta)^2 \cdot n$$\delta$

$\delta = \frac{\log(1/\varepsilon)}{n}$$\varepsilon$$\approx n - 2\log(1/\varepsilon)$