Take the 2-minute tour ×
Cross Validated is a question and answer site for people interested in statistics, machine learning, data analysis, data mining, and data visualization. It's 100% free, no registration required.

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 sum 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}[ X \geq \epsilon\sigma^2 N] \leq \exp(?)$, where $X = \sum_{i=1}^{N} w_iv_i$, $w_i$ and $v_i$ are generated i.i.d. from $\mathcal{N}(0, \sigma)$.

I tried to use the Chernoff bound using moment generating function (MGF), the derived bound is given by:

$\begin{eqnarray} \mathrm{Pr}[ X \geq \epsilon\sigma^2 N] &\leq& \min\limits_s \exp(-s\epsilon\sigma^2 N)g_X(s) \\ &=& \exp\left(-\frac{N}{2}\left(\sqrt{1+4\epsilon^2} -1 + \log(\sqrt{1+4\epsilon^2}-1) - \log(2\epsilon^2)\right)\right) \end{eqnarray}$

where $g_X(s) = \left(\frac{1}{1-\sigma^4 s^2}\right)^{\frac{N}{2}}$ is the MGF of $X$. But the bound is 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
    
Have you tried truncating the random variables? –  charles.y.zheng May 26 '11 at 19:33
    
I did not use, can you propose me a book or a paper to know how to do this. –  Farzad May 26 '11 at 19:46
    
@Farzad, if you do not get answers here try math.SE or mathoverflow.net. Why do you have sum of product of normal variable, is there a special reason? Also can you elaborate more on what tightness of the bound means? –  mpiktas May 26 '11 at 20:06
    
Sounds like a compressed-sensing related problem. Look up R. Vershynin's notes on nonasymptotic random matrix theory, specifically the bounds on what he calls subexponential random variables. That'll get you started. If you need more pointers, let us know and I'll try to post some more info. –  cardinal May 26 '11 at 20:14
1  
The product $w_i v_i$ has as a 'normal product' distribution. I believe the the mean of this product is zero and the variance is $\sigma^4$ where $\sigma^2$ is the variance of $w_i$ and $v_i$. For $N$ largeish, you could use the central limit theorem to get approximate norality of $X$. If you can compute the skew of the normal product distribution, I believe you can apply the Berry-Esseen theorem to bound the rate of convergence of the CDF. –  shabbychef May 26 '11 at 22:05
show 12 more comments

1 Answer 1

There is a new book on probability inequalities you could take a look at.

share|improve this answer
add comment

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.