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

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

share|improve this question
    
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
2  
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

1 Answer 1

up vote 1 down vote accepted

This is a standard exercise in large deviations. The exponential rate of decay for the large deviations of sums of i.i.d. random variables can be derived using Cramer's Theorem (see section 2.2 in Dembo and Zeitouni's book).

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

share|improve this answer
    
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
    
Thanks for your answer, can you give me the name of the book? –  Farzad May 26 '11 at 20:43
    
@Jon: Strict upper bound in the sense of nonasymptotic upper bound, I guess. –  Did May 27 '11 at 6:01
    
@Jon: Thanks a lot for your answer, but what about the case that we have a linear combination of RVs instead of the summation? I mean $X =\sum_{i=1}^{N} \alpha_i w_i v_i$, where $\alpha_i$ is deterministic. –  Farzad May 27 '11 at 11:36

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.