Welcome to MathOverflow

Question

5

2

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.

edited Aug 22 at 6:37

asked Aug 1 at 8:32

Tom Gur
105●1●4

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 at 12:55

That's not convolution, it's correlation. – Kevin O'Bryant Aug 1 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 at 15:58

1

Oups - all elements have order 2 so that +=-. – R W Aug 1 at 17:08

1

This question was later posted to cstheory.stackexchange.com: cstheory.stackexchange.com/q/12343/636 – Colin McQuillan Aug 21 at 18:18

show 2 more comments

Adrian Leverkuhn · Answer 1 · 2012-09-18 18:16:06Z UTC

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 ?

answered Sep 18 at 18:16

Adrian Leverkuhn
11●1

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 at 18:21

Bounding the entropy of a convolution

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

1 Answer

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.