Energy of repeated filter

Question

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.

Answer 1

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