Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Say we have a function $f:\mathbb{Z}_2^n \to \mathbb{R}$, such that $\sum _{x\in \mathbb{Z}_2^n} f(x)^2 = 1$ (so we can think of $\{ f(x)^2\} _{x\in \mathbb{Z}_2^n}$ as a distribution). It is natural to define the entropy of such function $f$ as follows: $$H(f) = -\sum _{x \in \mathbb{Z}_2^n} f(x)^2 \log \left( f(x)^2 \right) .$$

Now, consider the convolution of $f$ with itself: $$ \[ f*f\] (x) = \sum_{y \in \mathbb{Z}_2^n}f(y)f(x+y) .$$ (Since we are dealing with $\mathbb{Z}_2^n$, then $x+y=x-y$)

Is it possible to upper bound the entropy of $f*f$ (normalized in its $L_2$-norm, in order for it to be a distribution)? Formally, is there any constant $C$ such that $$ H \left( \frac{f*f}{\|f*f\|_2} \right) \le C \cdot H(f)$$

Note: This question was later posted to cstheory.stackexchange.com: cstheory.stackexchange.com/q/12343/636, where it was answered by Colin McQuillan.

share|improve this question
1  
Usually when you convolve measures, the entropy tend to grow, because the measure gets smoother (and in many occasions, smoother means also more spread-out). –  Asaf Aug 1 '12 at 12:55
    
That's not convolution, it's correlation. –  Kevin O'Bryant Aug 1 '12 at 14:08
1  
Why is this not (also) a convolution? We are in $\mathbb{Z}_2^n$. This might be a silly question because I did not think about this question yet, but are you looking for a constant $C$ independent of $n$? –  Tapio Rajala Aug 1 '12 at 15:58
1  
Oups - all elements have order 2 so that +=-. –  R W Aug 1 '12 at 17:08
2  
This question was later posted to cstheory.stackexchange.com: cstheory.stackexchange.com/q/12343/636 –  Colin McQuillan Aug 21 '12 at 18:18

1 Answer 1

Just a question/remark: Presumably you want $f$ to be nowhere zero otherwise I'm not sure what you mean by $f^2(x) \text{log} f^2(x)$ when $f(x) = 0$. Perhaps by fiat, and with the ghost of L'Hôpital's rule in the background, you simply declare $f^2(x) \text{log} f^2(x)$ to be zero whenever $f(x)$ is ?

share|improve this answer
1  
@Adrian, in entropy theory, $0 \log(0)\equiv 0$, you can justify that either by l'Hopital (when appropriate) or just take that as a definition. In any case, Colin already answered the question in stackexchange –  Asaf Sep 18 '12 at 18:21

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.