Probability inequalities

Hi everyone,

I am looking for some probability inequalities for sums of unbounded random variables. I would really appreciate it if anyone can provide me some thoughts.

My problem is to find an exponential upper bound over the probability that the linear combination of unbounded i.i.d. random variables, which are in fact the multiplication of two i.i.d. Gaussian, exceeds some certain value, i.e., $\mathrm{Pr}[\lvert X \rvert \geq \epsilon] \leq \exp(?)$, where $X = \sum_{i=1}^{N} \alpha_i w_iv_i$, $w_i$ and $v_i$ are generated i.i.d. from $\mathcal{N}(0, \sigma)$, and $0 \leq \alpha_i \leq 1$ is a coefficient.

I tried to use the Chernoff bound using moment generating function (MGF), but the derived bound was not so tight. The main issue in my problem is that the random variables are unbounded, and unfortunately I can not use the bound of Hoeffding inequality.

I will be to happy if you help me find some tight exponential bound . Thanks in advance

• Not clear what you're hoping to get here. Are you thinking of epsilon as small? In that case the probability will be close to 1/2 as $X$ will either be positive or negative (with equal probability); and will be close to 0 only with small probability. The probability of $|X|$ being less than $\epsilon$ should be about $\epsilon/\sqrt{\sigma N}$. – Anthony Quas May 26 '11 at 15:02
• Let $w=(w_1,\dots,w_n)$ and $v=(v_1,\dots,v_n)$. By isotropy and independence between $w$ and $v$, $X$ has the same law as $<w,\|v\|_2e_1>$ which is $\|v\|_2w_1$. The law of $\|v\|_2$ and of $w_1$ are standard laws and the two r.v.\ are independent. Is it sufficient for your purpose ? – camomille May 26 '11 at 16:00
• Dear Anthony, Thanks a lot for your answer but I need an upper bound over the probability not an approximate value. Dear Cammomille, Thanks a lot for your answer Unfortunately I did not understand what do you mean as law''. – Farzad May 26 '11 at 19:42
• law means distribution here. – camomille May 26 '11 at 19:55
• If I understood correctly, $X$ has the same distribution as $\lVert v \rVert_2 w$ whare $\lVert v \rVert_2$ has a chi distribution and $w_1$ has a Gaussian. Then, I can find the probability distribution of $X$? – Farzad May 26 '11 at 20:37

In the statement of the problem above, Cramer's theorem gives that $$P(|X| > \epsilon ) = e^{ - N I(\epsilon) + o(N) },$$ where $I(x)$ is the large deviation rate function. In this example (unless I screwed up in my calculation) $$I(x) = \frac{1}{2}\left( \sqrt{1+4x^2}-1+\log(\sqrt{1+4x^2}-1)-\log(2x^2) \right) .$$
• Cramer's theorem just gives exponential rate of decay. More precise asymptotics are $$P(|X| > \epsilon ) \sim \frac{C}{\sqrt{N}} e^{-N I(\epsilon)},$$ where the constant $C$ depends on $\epsilon$ and can be explicitly calculated in this case (see Theorem 3.7.4 in Dembo and Zeitouni's book). – Jon Peterson May 26 '11 at 20:20
• Farzad, in your comment above you mentioned that you needed an upper bound. An examination of the proof of the upper bound in Cramer's theorem shows that the exponential rate of decay given by the large deviation rate function is a strict upper bound. That is, $P(|X| > \epsilon ) \leq e^{-N I(\epsilon)}$ for all $\epsilon>0$ and all $N\geq 1$. – Jon Peterson May 26 '11 at 20:28
• Actually, in this case the coefficients are decaying so fast, the infinite random sum $\sum_{i=1}^\infty \alpha_i w_i v_i$ actually converges almost surely. Therefore, $P(|X|>\epsilon)$ doesn't decay at all but converges to a non-zero constant. – Jon Peterson May 27 '11 at 19:54