The entropy of a noisy distribution

Say we have a function $f:\mathbb{Z}_2^n \to \mathbb{R}$ such that $$\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\},$$ and $f$ is a distribution, i.e., $\sum_{x\in \mathbb{Z}_2^n} f(x) = 1$.

The Shannon entropy of $f$ is defined as follows: $$H(f) = -\sum _{x \in \mathbb{Z}_2^n} f(x) \log \left( f(x) \right) .$$

Let $\epsilon$ be some constant. Say we get an $\epsilon$-noisy version of $f(x)$, i.e., we get a function $\tilde{f}:\mathbb{Z}_2^n \to \mathbb{R}$ such that $|\tilde{f}(x)- f(x) | < \epsilon$ for every $x\in \mathbb{Z}_2^n$. What is the effect of the noise on the entropy? That is, can we bound $H(\tilde{f})$ by a "reasonable" function of $\epsilon$ and $H(f)$, such as: $$(1-\epsilon)H(f) < H(\tilde{f}) < (1+\epsilon)H(f),$$ or even, $$(1-\epsilon^c n)^d H(f) < H(\tilde{f}) < (1+\epsilon^c n)^d H(f),$$ for some constants $c,d$.

Edit: Trying to get a feeling for the effect of noise on Shannon's entropy, any "reasonable" additive bound on $H(\tilde{f})$ would also be very interesting.

Asked by user887 (0 )
Aug 24, 2012 at 09:11