Entropia głośnego rozkładu

Powiedzmy, że mamy funkcję $f:\mathbb{Z}_2^n \to \mathbb{R}$takie, że a jest rozkładem, tzn. .

$$\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$

Entropia Shannona dla jest zdefiniowana następująco: $f$

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

Niech będzie niezmienny. Powiedzmy, że otrzymujemy bezgłośną wersję , tj. Otrzymujemy funkcję taki że dla każdego . Jaki jest wpływ hałasu na entropię? To znaczy, czy możemy powiązać Przez „rozsądną” funkcję i , taką jak: a nawet dla niektórych stałych .$\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$$H(f)$

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

Edycja: Próbując wyczuć wpływ hałasu na entropię Shannona, każdy „rozsądny” dodatek związany z również byłby bardzo interesujący.$H(\tilde{f})$

Takie ograniczenie nie jest możliwe. Rozważ przypadek, w którym$f$ to rozkład, który jest równomierny w pewnym zbiorze $S$ wielkościowy $2^{\delta \cdot n}$, i pozwól $\tilde{f}$ być rozkładem, który z prawdopodobieństwem $\delta$ wyprowadza równomiernie rozłożony element $S$, a poza tym generuje równomiernie rozłożony ciąg.

Nietrudno dostrzec, że można to uzyskać $f$ do $\tilde{f}$ potrzebujesz tylko co najwyżej hałasu $(1-\delta) \cdot 2^{-\delta \cdot n}$. Jednak,$H(f)= \delta \cdot n$ podczas $H(\tilde{f}) \approx (1 - \delta + \delta^2) \cdot n$. Otrzymujesz różnicę$(1 - \delta)^2 \cdot n$ dla arbitralnie małych $\delta$ dla wyjątkowo niskiego poziomu hałasu.

W szczególności możesz ustawić $\delta = \frac{\log(1/\varepsilon)}{n}$i uzyskaj hałas $\varepsilon$ i różnica entropii $\approx n - 2\log(1/\varepsilon)$.