For given sequences $a=(a_1, a_2, \cdots)$ and $b=(b_1, b_2, \cdots)$, define $$a \star b$$ as the convolution. Formally, $$c=a \star b$$ implies the $i$th element of $c$, $c_i$, satisfies the following. $$c_i = \sum_{1 \leq n \leq i-1} a_n b_{i-n}$$.

Then, let a sequence $h=(h_1, h_2, \cdots)$ satisfies $h_i \in \mathbb{R}$ and $\sum_{1 \leq i \leq \infty} h_i = 1$.

Also define $h^{(n)}:=\underbrace{h \star \cdots \star h}_{\mbox{n times}}$. $h_i^{(n)}$ is the $i$ element of $h^{(n)}$.

(Prove or Find a counterexample for the following statement) There exists a constant $k > 0$ which only depends on $h$, and for all $n \in \mathbb{N}$, $$\sum_{1 \leq i \leq \infty} (h_i^{(n)})^2 \geq \frac{k}{\sqrt{n}}$$.

In other words, if we repeatedly convolve the same sequence the energy decreases in squared root at fastest. ---- I could prove the statement is true when $h_i \geq 0$ by considering $h$ as a probability distribution of a random variable. But I don't know for the case of $h_i \in \mathbb{R}$.

Here is the proof for the case of $h_i \geq 0$. Let's say $X$ be a random variable such that $\mathbb{P}(X=i) = h_i$ for all $i \in \{1,2,\cdots \}$. We also say $X_1, X_2, \cdots$ are i.i.d. random variables whose distribution is equal to $X$.

Then, the variance of $X_1+X_2+\cdots+X_n$ is $n \sigma^2$ where $\sigma^2$ is the variance of $X$. The entropy of $X_1+X_2+\cdots+X_n$, $H(X_1+X_2+\cdots+X_n)$, is approximately upper bounded by $\frac{1}{2}\log(2 \pi e n \sigma^2)$. (Gaussian and Poisson maximize the entropy given variance constraint.) Furthermore, since the distribution of $X_1+\cdots+X_n$ is $h^{(n)}$, $H_2(X_1+X_2+\cdots+X_n)$ (see http://en.wikipedia.org/wiki/Renyi_entropy) is equal to $\log \frac{1}{\sum_{1 \leq i \leq \infty} (h_i^{(n)})^2}$.

Since $H(X_1+X_2+\cdots+X_n) \geq H_2(X_1+X_2+\cdots+X_2)$ (see http://en.wikipedia.org/wiki/Renyi_entropy), we get $\frac{1}{2}\log(2 \pi e n \sigma^2) \geq \log \frac{1}{\sum_{1 \leq i \leq \infty} (h_i^{(n)})^2}$ which finishes the proof.

  • $\begingroup$ Is this a homework problem? $\endgroup$ – Noah Schweber Jan 24 '14 at 0:00
  • $\begingroup$ No. Absolutely not. $\endgroup$ – Seyong Jan 24 '14 at 0:03
  • $\begingroup$ There is some confusion with indices of your sequences: sometimes they run from $1$ to $\infty$, sometimes from $-\infty$ to $\infty$. Please correct. $\endgroup$ – Alexandre Eremenko Jan 24 '14 at 0:11
  • $\begingroup$ Sorry for the confusion. I corrected it $\endgroup$ – Seyong Jan 24 '14 at 0:15

This cannot be true. Let $f(e^{it})=\sum_n h_ne^{int}$, the generating function. Then $f^m$ will be the generating function of the $m$-th convolution $h_n^{(m)}$ of the sequence $(h_n)$ with itself. Now we have Parseval's equality, $$\frac{1}{2\pi}\int_0^{2\pi}|f(e^{it})|^{2m}dt=\sum_n |h_n^{(m)}|^2,$$ which is obtained by direct computation.

If you take $|f(e^{it})|<1/2$ for all $t$, the integral will decrease like $2^{-n}$.

Now you added the condition that $\sum h_n=1$. This translates to $f(1)=1$. Take $g(t)=\max\{ 0,1-|t|\}$. Simple computation shows that the integral with $g$ in place of $f(e^{it})$ decreases like $c/n$. Of course, in the expansion $$g(t)=\sum_n c_ne^{int}$$ we do not have $c_n=0$ for $n<0$, as you require.

But there is a simple way around this. Your condition that $h_n=0$ for $n<0$ translates into the condition that $f(e^{it})$ is the boundary value of a function analytic in the unit disc $|z|<1$. So $f(e^{it})$ cannot be arbitrarily prescribed. However $|f(e^{it})|$ can be (almost) arbitrarily prescribed, namely every continuous function strictly positive on the unit circle is the absolute value of the boundary values of a function analytic in the unit disc. (Just take $\log$ of this continuous function, solve the Dirichlet problem, attach the complex conjugate and exponentiate). So we can make $|f(e^{it})|=\max\{ 1/2,1-|t|\}$, for example. The integral will decrease as $c/n$.

  • $\begingroup$ I have the condition that $\sum_{1 \leq i \leq \infty} h_i =1$ $\endgroup$ – Seyong Jan 24 '14 at 0:38
  • $\begingroup$ I will edit and explain what I did for positive $h_i$ case. $\endgroup$ – Seyong Jan 24 '14 at 0:39
  • 2
    $\begingroup$ You also assume finite variance. Please state ALL assumptions you are willing to make. $\endgroup$ – Alexandre Eremenko Jan 24 '14 at 5:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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